Binary Tree Inorder Traversal (Medium)

Description

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

1
2
3
4
5
6
7
8
9
10
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?

Analysis

非递归实现树的中序遍历。用栈模拟，把所有左节点进栈。然后不断pop,顺便判断一下是否存在右孩子

My Solution

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