Monday, November 10, 2014

[LeetCode] 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?


1. 递归解法:

连题目都说recursive solution is trivial,没啥好说的,这解法两分钟写不出来就要被鄙视了。

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


2. 迭代解法:

面试中应该不会只考递归这么简单。所以迭代解法才是真正的重点。


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

1 comment: