LeetCode Binary Tree Inorder Traversal

1.题目

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?

2.解决方案1

class Solution {  
public:  
    vector<int> inorderTraversal(TreeNode *root) {  
        vector<int> path;  
        stack<TreeNode *> st;  
        if (root == NULL)  
            return path;  
        TreeNode *p = root;  
        while (p != NULL || !st.empty())  
        {  
            while (p != NULL)  
            {  
                st.push(p);  
                p = p->left;  
            }  
            if (!st.empty())  
            {  
                p = st.top();  
                st.pop();  
                path.push_back(p->val);  
                p = p->right;  
            }  
        }  
        return path;  
    }  
};

思路:中序遍历是先访问左节点，再访问中，再访问右。用一个stack来辅助，我们把一个节点的左节点全部入stack，然后再弹出最左边的节点。然后把当前的变量指针指向它的右节点，同样把右节的全部左节点入stack，再一个个弹出。当然非递归的方式还是有点难的。

3.解决方案2

class Solution {  
public:  
    vector<int> result;  
    void inorder(TreeNode *root)  
    {  
        if (root == NULL)  
            return;  
        inorder(root->left);  
        result.push_back(root->val);  
        inorder(root->right);  
    }  
    vector<int> inorderTraversal(TreeNode *root) {  
        result.clear();  
        inorder(root);  
        return result;  
    }  
};

思路：递归版本还是非常简单。

http://www.waitingfy.com/archives/1622

数据结构 & 算法 | RSS 2.0 |