By

文章目录
  1. 1. Binary Tree Inorder Traversal
    1. 1.1. 题目
    2. 1.2. 思路　
    3. 1.3. 解题

Binary Tree Inorder Traversal

题目

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?

思路　

不断地将当前节点压入到栈中，当前结点等于结点的左结点，直至左结点为NULL。将栈中最顶端的结点的值push_back到result中，当前结点等于最顶端结点的右结点，栈中最顶端结点出栈。 重复上述操作，直至当前节点为空以及栈为空。

解题

c++版

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
27
28
29
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode *> myStack;
        TreeNode *cur=root;
        while(cur || !myStack.empty()){
            while(cur){
                myStack.push(cur);
                cur=cur->left;
            }
            if(!myStack.empty()){
                result.push_back(myStack.top()->val);
                cur=myStack.top()->right;
                myStack.pop();
            }
        }
        return result;
    }
};

python版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def inorderTraversal(self, root):
        T=root
        s=[]
        result=[]
        while(T or (len(s)!=0)):
            while(T):
                s.append(T)
                T=T.left
            if(len(s)!=0):
                tmp=s[-1]
                result.append(tmp.val)
                s.pop()
                T=tmp.right
        return result

c++ 栈版

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
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<pair<TreeNode*,int>> ss;
        ss.push(make_pair(root,0));
        while(!ss.empty()){
            TreeNode* tmp=ss.top().first;
            if(tmp==NULL)
                ss.pop();
            else{
                switch(ss.top().second++){
                    case 0:
                        ss.push(make_pair(tmp->left,0));
                        break;
                    case 1:
                        result.push_back(tmp->val);
                        ss.pop();
                        ss.push(make_pair(tmp->right,0));
                        break;
                }
            }
            
        }
        return result;
    }
};

leetcode
leetcode,tree
文章目录
  1. 1. Binary Tree Inorder Traversal
    1. 1.1. 题目
    2. 1.2. 思路　
    3. 1.3. 解题