94. Binary Tree Inorder Traversal

描述

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?

解法

递归

中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。

中序遍历的递推公式：

inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)

加入条件判断可以减少函数调用，增加效率。

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        ret = []
        self.helper(root, ret)

        return ret

    def helper(self, root, ret):
        if not root:
            return

        if root.left:
            self.helper(root.left, ret)

        ret.append(root.val)

        if root.right:
            self.helper(root.right, ret)

时间复杂度：$O(n), T(n) = 2 \cdot T(n/2)+1$。

空间复杂度：最坏情况下 $O(n)$，平均情况下 $O(\log n)$，$n$ 为节点数目。

迭代

迭代需要使用栈记录节点。

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        ret = []
        cur = root

        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left

            cur = stack.pop()
            ret.append(cur.val)
            cur = cur.right

        return ret

# another iteratively
def inorderTraversal(self, root):
    res, stack = [], []
    while True:
        while root:
            stack.append(root)
            root = root.left
        if not stack:
            return res
        node = stack.pop()
        res.append(node.val)
        root = node.right

莫里斯遍历

在这种方法中，我们必须使用一种新的数据结构——线索二叉树，策略如下:

步骤1:将当前节点初始化为根节点

步骤2:如果当前节点不为空，

If current does not have left child

    a. Add current’s value

    b. Go to the right, i.e., current = current.right

Else

    a. In current's left subtree, make current the right child of the rightmost node

    b. Go to this left child, i.e., current = current.left

例如：

          1
        /   \
       2     3
      / \   /
     4   5 6

首先，1 是根节点，所以初始化 1 为 current, 1 有左子树，也就是 2, current 的左子树是

         2
        / \
       4   5

所以在这个子树中，最右边的节点是5，然后让 current(1) 作为 5 的右子节点。Set current = cuurent, left (current = 2)。树现在看起来像这样

         2
        / \
       4   5
            \
             1
              \
               3
              /
             6

对于当前的 2，它有左孩子 4，我们可以继续上面的过程

        4
         \
          2
           \
            5
             \
              1
               \
                3
               /
              6

然后添加4，因为它没有左子节点，然后依次添加2、5、1、3，对于左子节点6的节点3，执行上面的操作。最后，逆序是[4,2,5,1,6,3]。