Tree Traversal

一般思路

  • recursive
    • 很简单，就不说了
  • iterative, 用stack
    • time O(n) space是stack的高度O(logn)
  • Morris的方法！
    • space是O(1)的
    • 这种做法主要是利用叶子节点中的有空指针指向中序遍历下的successor
    • in-order和pre-order在方法上是一样的，只不过访问节点的时机不同

Morris的基本思想是

curr表示当前走到的node

  1. 如果curr没有left child, 将其输出，并且curr = curr.right
  2. curr有left child
    • 找到其predecessor,在中序遍历就是左子树的rightmost child
    • 将predecessor的right child设为curr，然后curr = curr.left
    • 如果已经是curr了，说明左子树已经遍历完了
      • 将right child重新设为None(恢复树结构)
      • 输出curr
      • curr = curr.right

时间复杂度

一开始以为是O(nlogn),因为找predecessor是logn。但是分析后我们可以发现， 每条边最多走两次：

  1. 定位到某个节点
  2. 寻找上面某个节点的predecessor

n个node的tree中有n-1条边，所以时间复杂度是O(n)

pre-order

iterative stack

def preOrder(root):
    result = []
    stack = []
    curr = root
    while curr or stack:
        if curr:
            stack.append(curr)
            result.append(curr.val) # pre-order
            curr = curr.left
        else:
            node = stack.pop()
            curr = node.right
    return result

Morris

def preOrder(root):
    result = []
    cur = root
    pre = None
    while cur:
        if cur.left is None:
            result.append(cur.val)
            cur = cur.right
        else:
            pre = cur.left
            while pre.right and pre.right != cur:
                pre = pre.right
            if pre.right is None:
                result.append(cur.val)
                pre.right = cur
                cur = cur.left
            else:
                pre.right = None
                cur = cur.right
    return result

in-order

recursive

class Solution:
    # @param A : root node of tree
    # @return a list of integers
    def inorderTraversal(self, A):
        result = []
        self.helper(A, result)
        return result

    def helper(self, A, result):
        if not A:
            return
        self.helper(A.left, result)
        result.append(A.val)
        self.helper(A.right, result)

stack

依然是利用stack，不过这里node是在左子树所有node都输出之后才输出到result list上。我们要维护一个curr变量来记录走到的node（不是输出的node），输出永远 是当前node的左子树都放到stack上之后才从stack上pop输出

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param A : root node of tree
    # @return a list of integers
    def inorderTraversal(self, A):
        result = []
        stack = []
        curr = A

        while curr or stack: # cause curr can be None sometimes
            if curr:
                stack.append(curr)
                curr = curr.left
            else:
                # left is done, can pop now
                node = stack.pop()
                result.append(node.val)
                curr = node.right # 注意！

        return result

Morris

class Solution:
    # @param A : root node of tree
    # @return a list of integers
    def inorderTraversal(self, A):
        result = []
        curr = A

        while curr:
            if curr.left is None:
                result.append(curr.val)
                curr = curr.right
            else:
                # find predecessor in left subtree
                prede = curr.left
                while prede.right and prede.right != curr:
                    prede = prede.right
                # use predecessor's right pointer
                if prede.right != curr:
                    prede.right = curr
                    curr = curr.left
                else:
                    # left subtree is done
                    prede.right = None
                    result.append(curr.val)
                    curr = curr.right
        return result

post-order

stack

需要维护一个curr和pre来判断

class Solution:
    # @param A : root node of tree
    # @return a list of integers
    def postorderTraversal(self, A):
        result = []
        stack = []
        curr = A
        pre = None

        while curr or stack:
            if curr:
                stack.append(curr)
                curr = curr.left
            else:
                peek = stack[-1]
                if peek.right and peek.right != pre:
                    curr = peek.right # careful!
                else:
                    stack.pop()
                    result.append(peek.val)
                    pre = peek
        return result

Morris

也需要curr和pre,还要一个subrroutin将rightmost in lefttree到left child的path reverse 输出一下。

class Solution:
    # @param A : root node of tree
    # @return a list of integers
    def postorderTraversal(self, A):
        result = []
        curr = A
        dummy = TreeNode(0)
        dummy.left = A
        curr = dummy

        while curr:
            if curr.left is None:
                curr = curr.right
            else:
                pre = curr.left
                while pre.right and pre.right != curr:
                    pre = pre.right
                if pre.right != curr:
                    pre.right = curr
                    curr = curr.left
                else:
                    self.reverse(curr.left, pre)
                    tmp = pre
                    while tmp != curr.left:
                        result.append(tmp.val)
                        tmp = tmp.right
                    result.append(tmp.val)
                    self.reverse(pre, curr.left)
                    pre.right = None
                    curr = curr.right

        return result

    def reverse(self, start, end):
        if start == end:
            return
        pre = start
        curr = start.right
        while pre != end:
            n = curr.right
            curr.right = pre
            pre = curr
            curr = n

Reference