[LeetCode 94] Binary Tree Inorder Traversal

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

For example:
Given binary tree [1,null,2,3],

1
 \
  2
 /
3

return [1,3,2].

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

Diffculty
Medium

Similar Problems
[LeetCode ] Validate Binary Search Tree Medium [LeetCode ] Binary Tree Preorder Traversal Medium [LeetCode ] Binary Tree Postorder Traversal Hard [LeetCode ] Binary Search Tree Iterator Medium [LeetCode ] Kth Smallest Element in a BST Medium [LeetCode ] Closest Binary Search Tree Value II Hard [LeetCode ] Inorder Successor in BST Medium

Analysis

二叉树的遍历，通常是深度优先，有两种实现方式，一是递归，二是非递归。 由于每个节点只会访问一次，因此时间复杂度是 O(N)。空间复杂度通常是 O(logN)。 这道题，还有一种空间复杂度 O(1) 的解法，叫做 Morris Traversal。

Morris Traversal。想用O(1)空间进行遍历，因为不能用栈作为辅助空间来保存付节点的信息，重点在于当访问到子节点的时候如何重新回到父节点（当然这里是指没有父节点指针，如果有其实就比较好办，一直找遍历的后驱结点即可）。Morris遍历方法用了线索二叉树，这个方法不需要为每个节点额外分配指针指向其前驱和后继结点，而是利用叶子节点中的右空指针指向中序遍历下的后继节点就可以了。 算法具体分情况如下：

  1. 如果当前结点的左孩子为空，则输出当前结点并将其当前节点赋值为右孩子。
  2. 如果当前节点的左孩子不为空，则寻找当前节点在中序遍历下的前驱节点（也就是当前结点左子树的最右孩子）。接下来分两种情况： a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点（做线索使得稍后可以重新返回父结点）。然后将当前节点更新为当前节点的左孩子。 b) 如果前驱节点的右孩子为当前节点，表明左子树已经访问完，可以访问当前节点。将它的右孩子重新设为空（恢复树的结构）。输出当前节点。当前节点更新为当前节点的右孩子。

Solutions

  1. 递归
vector<int> inorderTraversal(TreeNode *root) {  
  vector<int> res;  
  inorder(root, result);  
  return result;  
}  
void inorder(TreeNode* node, vector<int> &res){
   if(node == nullptr) return; 
   inorder(node->left, res);  
   res.push_back(node->val);      
   inorder(node->right, res);  
}
  1. 非递归
vector<int> inorderTraversal(TreeNode *root) {  
    vector<int> res;
    if(root == NULL) return res;  
    stack<TreeNode*> st;
    st.push(root);
    while(root != nullptr || !st.empty()) {
        if (root != nullptr) {
            st.push(root);
            root = root->left;
        } else {
            root = st.top();
            st.pop();
            res.push_back(root);
            root = root->right;
        }
    }
    return res;
}
  1. Morris 遍历
void inorderMorrisTraversal(TreeNode *root) {
    TreeNode *cur = root, *prev = NULL;
    while (cur != NULL) {
        if (cur->left == NULL) {          // 1.
            printf("%d ", cur->val);
            cur = cur->right;
        }
        else {
            // find predecessor
            prev = cur->left;
            while (prev->right != NULL && prev->right != cur)
                prev = prev->right;
            if (prev->right == NULL) {   // 2.a)
                prev->right = cur;
                cur = cur->left;
            }
            else {                      // 2.b)
                prev->right = NULL;
                printf("%d ", cur->val);
                cur = cur->right;
            }
        }
    }
}

复杂度分析： 空间复杂度：O(1)，因为只用了两个辅助指针。 时间复杂度：O(n)。证明时间复杂度为O(n)，最大的疑惑在于寻找中序遍历下二叉树中所有节点的前驱节点的时间复杂度是多少，即以下两行代码： 1 while (prev->right != NULL && prev->right != cur) 2 prev = prev->right; 直觉上，认为它的复杂度是O(nlgn)，因为找单个节点的前驱节点与树的高度有关。但事实上，寻找所有节点的前驱节点只需要O(n)时间。n个节点的二叉树中一共有n-1条边，整个过程中每条边最多只走2次，一次是为了定位到某个节点，另一次是为了寻找上面某个节点的前驱节点，如下图所示，其中红色是为了定位到某个节点，黑色线是为了找到前驱节点。所以复杂度为O(n)。

results matching ""

    No results matching ""