leetcodeBinary Tree Inorder Traversal

时间：2015-05-10 17:19:29 收藏：0 阅读：205

题目描述

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

For example:
Given binary tree {1,#,2,3},

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

解题方法

中序遍历二叉树：递归方法：

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

迭代方法：

仿照前序遍历使用堆栈，不过是左节点先入栈，直到左孩子为空，出栈，入栈顶元素的右孩子，然后再入右子树的左孩子节点。依次直到堆栈为空，值得注意的是，中序遍历跟先序遍历起始不同的是，根节点不最先入栈！！！代码如下：

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

原文：http://blog.csdn.net/sinat_24520925/article/details/45621865