LeetCode/144_Binary_Tree_Preorder_Traversal.py at master · Lobo2008/LeetCode · GitHub

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
"""
Given a binary tree, return the preorder traversal of its nodes' values.

Example:

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

Output: [1,2,3]

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


"""

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

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        """
        前序遍历：根-左-右

        1）root=1存在，rs=[1] ->=[2,4,5]  ->r=[3,6,7]  ==>[1,2,4,5,3,6,7]
        2)访问左子树，存在
             2
           /  \
          4    5
            (1)root=2存在, rs_l=[2] ->[2,4,5]
            (2)访问左子树，存在  -> rs_l_l=[4]
                  4
                /   \
               no1  no2
                  root=4,存在，rs_l_l=[4]
                  访问左子树，不存在 ，rs_l_l=[4]
                  访问右子树，不存在 ，rs_l_l=[4]
                所以rs_l_l=[4]
             (3)访问右子树，存在rl_r_r= =[5]
        3)访问右子树，存在  -> [3,6,7]
            3
          /   \
         6     7


     1)root=1 存在，rs=[1],     stack=[1],    root=left=2
     2)root=2 存在，rs=[1,2],   stack=[1,2]     root=left=4
     3)root=4 存在，rs=[1,2,4], stack=[1,2,4]   root =left=null
     4)root=null不存在，stack弹出4->stack=[1,2]  相当于返回dad，root=4,然后访问右son，right=null
     5)root=null不存在，stack弹出2->stack=[1]    相当于返回dad，root=2，然后访问右son，right=5
     6)root=5 存在，rs=[1,2,4,5] stack=[1,5]  root=left=null
     7)......
"""
        rs = []
        stack = []
        while root or stack:
            if root:
                rs.append(root.val)
                stack.append(root) ####注意！！易错点，是append(root), 不是root.val
                root = root.left
            else:
                root = stack.pop()
                root = root.right
        return rs

    """
    前序遍历，递归方法
    """
    def preorderTraversal_recursive(self, root):

        rs = []
        self.recursive(root, rs)
        return rs
    def recursive(self, root,rs):
        if root:
            rs.append(root.val)
            self.recursive(root.left, rs)
            self.recursive(root.right, rs)


so = Solution()

1

l1 = TreeNode(1)
l2 = TreeNode(2)
l3 = TreeNode(3)
l4 = TreeNode(4)
l5 = TreeNode(5)
l6 = TreeNode(6)
l7 = TreeNode(7)

root = l1

l1.left = l2
l1.right = l3
l2.left = l4
l2.right = l5
l3.left = l6
l3.right = l7

print(so.preorderTraversal(root))
# print(so.preorderTraversal_recursive(root))


"""
             1
           /   \
          2     2
         / \   /  \
        3   4 4    3
       / \        / \
      5  6       6   5

      pre: [1,2,3,5,6,4,2,4,3,6,5]

 """

l1 = TreeNode(1)

l21 = TreeNode(2)
l22 = TreeNode(2)

l31 = TreeNode(3)
l32 = TreeNode(4)
l33 = TreeNode(4)
l34 = TreeNode(3)

l41 = TreeNode(5)
l42 = TreeNode(6)
l43 = TreeNode(6)
l44 = TreeNode(5)

root = l1

l1.left = l21; l1.right = l22

l21.left = l31; l21.right = l32
l22.left = l33; l22.right = l34

l31.left = l41; l31.right = l42
l34.left = l43; l34.right = l44
print(so.preorderTraversal(root))