LeetCode题目:Binary Tree Inorder Traversal

By | 2012 年 9 月 14 日

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?
confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

    代码

    /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    
  1. 递归解法
    很简单,8ms过小集合,12ms过大集合

    class Solution {
    public:
        vector inorderTraversal(TreeNode *root) {
            vector result;
            if (NULL == root)
                return result;
            vector leftResult = inorderTraversal(root->left);
            vector rightResult = inorderTraversal(root->right);
            for( int i = 0 ; i < leftResult.size(); ++i)
                result.push_back(leftResult[i]);
            result.push_back(root->val);
            for( int i = 0 ; i < rightResult.size(); ++i)
                result.push_back(rightResult[i]);
            return result;
        }
    };
    
  2. 循环解法
    稍复杂点,大小集合都是8ms过

    class Solution {
    public:
        vector inorderTraversal(TreeNode *root) {
            vector result;
            
            vector trace;
            TreeNode *cur = root;
            TreeNode *pre = NULL;
            bool forward = true;
            while(cur)
            {
                if (forward) 
                {
                    //have unvisited left
                    if (cur->left && pre != cur->left)
                    {
                        pre = cur;
                        trace.push_back(cur);
                        cur = cur->left;
                        continue;
                    }
                    forward = false;
                }
                else
                {
                    //not return from right, add self
                    if(cur->right == NULL || cur->right != pre)
                        result.push_back(cur->val);
                    //go right if could
                    if(cur->right && pre != cur->right)
                    {
                        forward = true;
                        pre = cur;
                        trace.push_back(cur);
                        cur = cur->right;
                        continue;
                    }
                    //go up
                    pre = cur;
                    if (trace.size() > 0)
                    {
                        cur = trace[trace.size() - 1];
                        trace.pop_back();
                    } else
                        cur = NULL;
                    
                }
            }
            
            return result;
        }
    };
    
  3. 循环解法,2012年12月6日重写,比上一个简洁
    class Solution {
    public:
        vector inorderTraversal(TreeNode *root) {
            // Start typing your C/C++ solution below
            // DO NOT write int main() function
            vector ret;
            if(NULL == root) return ret;
            
            bool forward = true;
            stack trace;
            TreeNode *preNode = NULL;
            trace.push(root);
            
            while(trace.size()) {
                TreeNode *curNode = trace.top();
                if(forward) {
                    if(curNode->left && preNode != curNode->left) {
                        trace.push(curNode->left);
                    } else {
                        //no left or left visited
                        forward = false;
                    }
                } else {
                    //backward, find sibling(right child)
                    //if not back from right child, then visit it
                    if(curNode->right != preNode)
                        ret.push_back(curNode->val);
                    if(curNode->right && preNode != curNode->right) {
                        //if have an unvisited right child, traval it.
                        trace.push(curNode->right);
                        forward = true;
                    } else {
                        //all sub-tree of this node is visited
                        trace.pop();
                    }
                }
                preNode = curNode;
            }
            
            return ret;
        }
    };
    

发表评论

电子邮件地址不会被公开。 必填项已用*标注