94. Binary Tree Inorder Traversal

porblem description

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

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

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

algorithm thought

二叉树的中序遍历问题。这种问题用递归的方法是很简单的。但是还是要知道迭代的写法。毕竟如果节点很多的话，那么多递归函数，栈开销会很大。

递归写法很简单，按顺序访问就行，对于迭代写法，我们首先要明白我们访问的顺序，先左，后中再右。我们使用一个栈保存中间节点，没碰到一个root节点，顺序将左子树一直push进栈，到叶子节点的时候，弹出顶上的节点，这时候就能访问了，然后对于这个节点的右子树，把它当做一个root，继续运行一遍

然后去看了一下discuss，真的是发现每次看都会发现很意想不到的算法。比如中序遍历，这里就可以用morris traversal，只需要O(1)的空间，时间复杂度还是控制在O(n)。极大的减少了空间。这里主要是利用了叶子节点大量的空指针。前面问题使用栈来辅助解决，是因为访问到后续节点的时候，不能够再回到根节点，这里用叶子节点的指针，指向后继节点，方便回到前面。

步骤是：

1. 如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。

2. 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。

a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。

b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子。

3. 重复以上1、2直到当前节点为空。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
//递归写法
class Solution {
public:
    vector<int> res; 
    void inorder(TreeNode* root)
    {
        if(root==NULL)
            return;
        inorder(root->left);
        res.push_back(root->val);
        inorder(root->right);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        inorder(root);
        return res;
    }
};


//迭代写法
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        while(root||!st.empty()){
            while(root){
                st.push(root);
                root=root->left;
            }
            root=st.top();
            st.pop();
            res.push_back(root->val);
            root=root->right;
        }
        return res;
    }
};

//morris 
lass Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;       
        TreeNode* prev=NULL;
        while(root){
            if(root->left==NULL){
                res.push_back(root->val);
                root=root->right;
            }else{
                prev=root->left;
                while(prev->right&&prev->right!=root){
                    prev=prev->right;
                }
                if(prev->right==NULL){
                    prev->right=root;
                    root=root->left;
                }else{
                    root=prev->right;
                    prev->right=NULL;
                    res.push_back(root->val);
                    root=root->right;
                }
            }
        }
        return res;
    }
};

algorigthm thought

通过分析和LeetCode最后的结果来说，上面3中方法从上到下应该是越来越好的。迭代对于递归来说，减少了函数栈开销，最后空间用的少一点。Morris对于上面两中来说，只用了O(1)的空间复杂度，最后空间是用的最少的。