Binary Tree Inorder Traversal

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

http://www.lintcode.com/en/problem/binary-tree-inorder-traversal/

Discussion

啥也不说了，递归迭代Morris三种方法都要熟。

Solution

Iteration. Using stack. O(n) run time, O(n) space.

class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Inorder in vector which contains node values.
     */
public:
    vector<int> inorderTraversal(TreeNode *root) {
        // write your code here
        vector<int> result;
        if(root == NULL) 
            return result;
        TreeNode *cur = root;
        stack<TreeNode*> mystk;
        while(cur) { //push the left chile first
            mystk.push(cur);
            cur = cur->left;
        }
        while(mystk.empty() == false) {
            cur = mystk.top();//mush on the most left
            mystk.pop();
            result.push_back(cur->val);
            cur = cur->right; //then its right child
            while(cur) {
                mystk.push(cur);
                cur = cur->left;
            }
        }
        return result;
    }
};

//初始化一个二叉树结点pNode指向根结点；
//若pNode非空，那么就把pNode入栈，并把pNode变为其左孩子；（直到最左边的结点）
//若pNode为空，弹出栈顶的结点，并访问该结点，将pNode指向其右孩子（访问最左边的结点，并遍历其右子树）
vector<int> inorderTraversal(TreeNode *root) {
        // write your code here
        vector<int> result;
        TreeNode *cur = root;
        stack<TreeNode*> mystk;
        while(cur != NULL || !mystk.empty()) {
            if(cur != NULL) {
                mystk.push(cur);
                cur = cur->left;
            } else {
                cur = mystk.top();
                mystk.pop();
                result.push_back(cur->val);
                cur = cur->right;
            }
        }
        return result;
    }

Recursion.

class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Inorder in vector which contains node values.
     */
public:
    vector<int> inorderTraversal(TreeNode *root) {
        // write your code here
        vector<int> result;
        reverse(root, result);
        return result;
    }
private:
    void reverse(TreeNode *root, vector<int> &result) {
        if(root == NULL) {
            return;
        }
        reverse(root->left, result);
        result.push_back(root->val);
        reverse(root->right, result);
    }
};

Morris. O(n) run time, O(1) space.

Morris 的核心就是利用叶子节点的右指针建立遍历关系，具体说来就是，找到每个非叶子节点cur左子树的最右叶子节点，让该叶子的right指向cur

class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Inorder in vector which contains node values.
     */
public:
    vector<int> inorderTraversal(TreeNode *root) {
        // write your code here
        vector<int> result;
        if(root == NULL) return result;
        TreeNode *cur = root;
        TreeNode *predecessor;
        while(cur != NULL) {
            if(cur->left == NULL) {
                result.push_back(cur->val);
                cur = cur->right;
            } else {
                predecessor = cur->left;
                while(predecessor->right !=NULL && predecessor->right != cur) {
                    predecessor = predecessor->right;
                }
                if(predecessor->right == NULL) {
                    predecessor->right = cur;
                    cur = cur->left;
                } else {
                    result.push_back(cur->val);
                    cur = cur->right;
                }
            }
        }
        return result;
    }
};