转载

LeetCode Binary Tree Inorder Traversal

1.题目

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:

Given binary tree {1,#,2,3} ,

1     /      2     /    3

return [1,3,2] .

Note:Recursive solution is trivial, could you do it iteratively?

2.解决方案1

class Solution {   public:    vector<int> inorderTraversal(TreeNode *root) {     vector<int> path;     stack<TreeNode *> st;     if (root == NULL)      return path;     TreeNode *p = root;     while (p != NULL || !st.empty())     {      while (p != NULL)      {       st.push(p);       p = p->left;      }      if (!st.empty())      {       p = st.top();       st.pop();       path.push_back(p->val);       p = p->right;      }     }     return path;    }   };

思路:中序遍历是先访问左节点，再访问中，再访问右。用一个stack来辅助，我们把一个节点的左节点全部入stack，然后再弹出最左边的节点。然后把当前的变量指针指向它的右节点，同样把右节的全部左节点入stack，再一个个弹出。当然非递归的方式还是有点难的。

3.解决方案2

class Solution {   public:    vector<int> result;    void inorder(TreeNode *root)    {     if (root == NULL)      return;     inorder(root->left);     result.push_back(root->val);     inorder(root->right);    }    vector<int> inorderTraversal(TreeNode *root) {     result.clear();     inorder(root);     return result;    }   };

思路：递归版本还是非常简单。

正文到此结束