Tree Traversal DFS

Algorithms
tree
Catalogue
  1. 1. Tree DFS
    1. 1.1. 144. Binary Tree Preorder Traversal
      1. 1.1.1. Recursion
      2. 1.1.2. Iteration (Stack)
    2. 1.2. 94. Binary Tree Inorder Traversal
      1. 1.2.1. Recursion
      2. 1.2.2. Iteration (Stack + cur)
    3. 1.3. 145. Binary Tree Postorder Traversal
      1. 1.3.1. Recursion
      2. 1.3.2. Iteration
        1. 1.3.2.1. 解法1. Two Stacks
        2. 1.3.2.2. 解法2. Stack + cur + prev
    4. 1.4. 590. N-ary Tree Postorder Traversal
    5. 1.5. 589. N-ary Tree Preorder Traversal
    6. 1.6. Morris Traversal

Tree DFS

  • Recursion vs Iteration.
    Too easy to use recursion to solve the traversal problem, Why we need the iterative solution?

Java meomory area

  • STACK: storing the local variables and other information for each of the method calls
  • HEAP: allocationg spaces for dynamically created objects
  • Threads have their own stack, but they share same heap!

Python内存中没有真正的堆栈，因为所有的对象都是在堆上分配的，but python默认的递归深度是很有限的（默认是1000）

  • STACK
    • In Java, STACK is usually a size limited memory area.By default, a several thousands levels recursion call would easily eat up all the space and throw StackOverFlowException - this is something you have to keep in mind
    • Iterative way is good because it needs much less space of STACK(There is probably only O(1) method call levels, so O(1) space on STACK.)
    • It is not easy to convert all recursion solutions to a “while loop” solution without any other auxiliary data structures’ help.
1
2
3
4
5
6
7
8
# Recursive Inorder Traversal
class Solution(object):
    def inorderTraversal(self, root):
        if not root:
            return []
        self.inorderTraversal(root.left)
        print(root.val)
        self.inorderTraversal(root.right)

  • There are two paths of recursion need to follow instead of one, and we need to finish the first branch, then the second one.

  • In this case, we will need something else to help us:

    • The recursion is internally done by using STACK to maintain the method call levels and directions, we can simulate this ourselves, so a stack will be needed.
    • The difference is, we use our own stack and the space used by our own stack is on HEAP. The space consumed on STACK is trivial.
    • We do not change the total space consumption, but we move out the space consumption of STACK to HEAP!!!

144. Binary Tree Preorder Traversal

Recursion

1
2
3
4
5
6
class Solution(object):
    def preorderTraversal(self, root):
        if not root: return []
        return ([root.val]
                + self.preorderTraversal(root.left)
                + self.preorderTraversal(root.right))

Iteration (Stack)

  • 1 stack一出栈 一看见就访问！
  • 2 出栈元素的右子节点先加入栈，再加左子节点
  • 每个node其实处理了两次，一次是入栈，一次是出栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def preorderTraversal(self, root):
        if not root:
            return []
        stack = [root]
        res = []
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res

94. Binary Tree Inorder Traversal

Recursion

1
2
3
4
5
6
7
class Solution(object):
    def inorderTraversal(self, root):
        if not root:
            return []
        left = self.inorderTraversal(root.left)
        right = self.inorderTraversal(root.right)
        return left + [root.val] + right

Iteration (Stack + cur)

The problem is, we can not throw away the root in the stack before we traversed all the nodes in left subtreee. How can we know we have already traversed all the nodes in left sub?

  • The root is the top element in the stack, use a helper node to store the next “visiting” node and subtree.
    • 1 When helper node is not null, we should traverse the subtree, so we push helper and we go left
    • 2 When helper is null, means the left subtree of the roots finished, the root is the top element in the stack. We can print the top, and let helper = top.right.(traverse the left subtree firtst, then top. then right subtree)
    • 3 do 1 and 2 until helper is null and there is no nodes left in the stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 写法1.
class Solution(object):
    def inorderTraversal(self, root):
        if not root:
            return []
        res, stack = [], []
        cur = root
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            res.append(cur.val)
            cur = cur.right
        return res

# 写法2.
class Solution(object):
def inorderTraversal(self, root):
    if not root:
        return []

    stack, res = [], []
    cur = root
    while stack or cur:
        if cur:
            stack.append(cur)
            cur = cur.left
        else:
            cur = stack.pop()
            res.append(cur.val)
            cur = cur.right
    return res

145. Binary Tree Postorder Traversal

Recursion

1
2
3
4
5
6
7
class Solution(object):
    def inorderTraversal(self, root):
        if not root:
            return []
        left = self.inorderTraversal(root.left)
        right = self.inorderTraversal(root.right)
        return left + right + [root.val]

Iteration

解法1. Two Stacks
  • left->right->root (reverse)=> root->right->left
  • Preorder -> Postorder
1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def postorderTraversal(self, root):
        # Pre-order, but root->right->left
        stack, res = [root], []
        while stack:
            node = stack.pop()
            if node:
                res.append(node.val)
                stack.append(node.left)
                stack.append(node.right)
        return res[::-1]
  • What is the drawback of two stacks solution, if we deal with the nodes on the fly? (Online)
    Need to store everything in memory before we can get the whole post order traversal sequenct.
解法2. Stack + cur + prev

The problem is, we need to traverse both left and right subtrees first, then we can eliminate the root from the stack. We need an mechanism to know, when we finished visiting all subtrees’ nodes.

  • What we need to know?

    • Direction!!!!!!!
    • we are visiting down? or returning from left? or returning from right?

  • 思路1. 细分三种case
    The root is the top element in the stack
    Maintain a previous Node, to record the previous visiting node on the tracersing path, so that we know what the direction we are taking now and what is the direction we are taking next.

    • root = stack.top
    • if previous is null -> going down(left subtree has priority)
    • if previous is current’parent -> going down (left subtree has priority)
    • if previous == current.left -> left subtree finished, going current.right
    • if previous == current.right -> right subtree finished, pop current, going up.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
# 思路写法
class Solution(object):
    def postorderTraversal(self, root):
        if not root:
            return []

        prev = None
        stack = [root]
        res = []
        while stack:
            cur = stack[-1]
            # Case1: 从父节点而来
            if not prev or cur == prev.left or cur == prev.right:
                if cur.left:
                    stack.append(cur.left)
                elif cur.right:
                    stack.append(cur.right)
                else: # 叶子节点
                    res.append(cur.val)
                    stack.pop()
            # Case2: 从左子树遍历完而来
            elif prev == cur.left:
                if cur.right:
                    stack.append(cur.right)
                else:
                    res.append(cur.val)
                    stack.pop()
            # Case3: 从右子树遍历完而来
            else:
                res.append(cur.val)
                stack.pop()
            prev = cur
        return res

# 简化写法
class Solution(object):
    def postorderTraversal1(self, root):
        if not root:
            return []

        prev = None
        stack = [root]
        res = []
        while stack:
            cur = stack[-1]
            # Case1: 从父节点而来
            if not prev or cur == prev.left or cur == prev.right:
                if cur.left:
                    stack.append(cur.left)
                elif cur.right:
                    stack.append(cur.right)
            # Case2: 从左子树遍历完而来
            elif prev == cur.left:
                if cur.right:
                    stack.append(cur.right)
            # Case3: 从右子树遍历完而来 或者 是叶子节点
            else:
                res.append(cur.val)
                stack.pop()
            prev = cur
        return res
  • 思路2 只划分上下两种case
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def postorderTraversal(self, root):
        if not root:
            return []

        prev = None
        stack, res = [root], []
        while stack:
            cur = stack[-1]
            # Case1: 什么时候访问节点？
            # 1.叶子节点 2.从子节点而来
            if (not cur.left and not cur.right) or (prev and (cur.right == prev or cur.left == prev)):
                node = stack.pop()
                res.append(node.val)
                prev = node
            # Case2: 从父节点而来
            else:
                if cur.right:
                    stack.append(cur.right)
                if cur.left:
                    stack.append(cur.left)
        return res
  • 什么时候访问root节点？
    • preorder: 直接访问 stack
    • inorder: 左subtree访问完了，再访问 stack+cur
    • postorder: 左右subtree访问完了，再访问 stack+cur+prev

590. N-ary Tree Postorder Traversal

  • Recursion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def postorder(self, root):
        res = []
        self.dfs(root, res)
        return res

    def dfs(self, root, res):
        if not root:
            return

        for child in root.children:
            self.dfs(child, res)

        res.append(root.val)
  • Iteration
    Use ‘Two Stack’ Postorder Traversal Way!
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def postorder(self, root):
        if not root:
            return []

        res = []
        stack = [root]
        while stack:
            node = stack.pop()
            res.append(node.val)
            for child in node.children:
                stack.append(child)
        return res[::-1]

589. N-ary Tree Preorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
# Iteration
class Solution(object):
    def preorder(self, root):
        if not root: return []

        stack = [root]
        res = []
        while stack:
            node = stack.pop()
            res.append(node.val)
            for child in node.children[::-1]:
                stack.append(child)
        return res

Morris Traversal

  • 1968年，Knuth提出说能否将该问题的空间复杂度压缩到O(1)，同时原树的结构不能改变。

  • 大约十年后，1979年，Morris在”Traversing Binary Trees Simply and Cheaply”这篇论文中用一种Threaded Binary Tree的方法解决了该问题。

  • Morris算法在遍历过程中动态的构建Threaded Binary Tree，同时在结束时又将树恢复原样，在满足O(1)空间复杂度的同时也恰好满足Knuth对树结构不能改变的要求。适合空间复杂度要求高的场合！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Inorder Demo Morris Traversal
class Solution(object):
    def inorderTraversal(self, root):
        if not root:
            return []
        res = []
        cur = root
        while cur:
            if not cur.left:
                res.append(cur.val)
                cur = cur.right
            else:
                # 1 Find Inorder Predecessor of cur
                prev = cur.left
                while prev.right and prev.right != cur:
                    prev = prev.right

                # 2 Connect or Restore the Pointer
                if not prev.right:
                    prev.right = cur
                    cur = cur.left
                else:
                    prev.right = None
                    res.append(cur.val)
                    cur = cur.right
        return res
Share