题目

中文

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
image.png

英文

题目注意点

无注意点 只是递归很简单，应该尝试迭代的方法。

题解

第一次

讲解

递归方法
递归方法很简单 就是几个语句的顺序不同。

  1. class Solution {
  2. public:
  3.     void inorder(TreeNode* root, vector<int>& res) {
  4.         if (!root) {
  5.             return;
  6.         }
  7.         inorder(root->left, res);
  8.         res.push_back(root->val);
  9.         inorder(root->right, res);
  10.     }
  11.     vector<int> inorderTraversal(TreeNode* root) {
  12.         vector<int> res;
  13.         inorder(root, res);
  14.         return res;
  15.     }
  16. };

栈 迭代方法：
思路：每到一个节点 A，因为根的访问在中间，将 A 入栈。然后遍历左子树，接着访问 A，最后遍历右子树。

再访问完 A 后，A 就可以出栈了。因为 A 和其左子树都已经访问完成。
伪代码

栈S;
p= root;
while(p || S不空){
    while(p){
        p入S;
        p = p的左子树;
    }
    p = S.top 出栈;
    访问p;
    p = p的右子树;
}

class Solution {
public:
       vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> S;
        vector<int> v;
        TreeNode* rt = root;
        while(rt || S.size()){
            while(rt){
                S.push(rt);
                rt=rt->left;
            }
            rt=S.top();S.pop();
            v.push_back(rt->val);
            rt=rt->right;
        }
        return v;        
    }
};

注意到

c++ 树的stl模板。
有一个颜色标记法，和Morris法 下次写。