Given a binary tree, return the preorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

1
2
3
4
5
1
 \
  2
 /
3

return [1,2,3].

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

思路

题目要求我们将树先序遍历，然后输出结果。

我们可以先简单地利用深度优先遍历，递归地得出结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 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]
        """
        self.res = []
        if (root):
            self.helper(root)
        return self.res
        
    def helper(self, root):
        self.res.append(root.val)
        if (root.left):
            self.helper(root.left)
        if (root.right):
            self.helper(root.right)

如果不用递归的方法，可以利用栈来进行树的先序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        if (root):
            stack = [root]
            
            while (stack):
                cur = stack.pop()
                res.append(cur.val)
                if (cur.right):
                    stack.append(cur.right)
                if (cur.left):
                    stack.append(cur.left)
        return res