Leetcode-94.二叉树的中序遍历

发表于 分类于 阅读次数：

题目链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

解法1：递归

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

解法2：迭代

用栈来暂存节点，先从根节点向左子树遍历放入栈中，然后输出栈顶元素，看右子树，循环操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
private:
    vector<int> res;
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode> s;
        TreeNode *t=root;
        while(t!=NULL||!s.empty())
        {
            while(t!=NULL)
            {
                s.push(*t);
                t=t->left;
            }
            if(!s.empty())
            {
                res.push_back(s.top().val);
                t=s.top().right;
                s.pop();
            }
        }
        return res;
    }
};