Binary Tree Preorder Traversal

题目描述

解题方法

这道题可以用递归解，也可以用iterative的方法来解，一般面试中考察iterative的方法

Solution

• 递归
• iterative stack
• morris方法

递归

因为在递归中的None的返回值与一开始root为None的返回值不一样，所以我们要用一个helper function, 在helper function中对result这个mutable的list进行修改。

# 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]
        """
        if not root:
            return []
        result = []
        self.helper(result, root)

        return result

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

iterative, 用stack

用一个stack来模拟这个过程，因为是Preorder，所以可以在一开始就将root加到stack上，然后再将right, leftpush到stack上。

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        result = []
        stack = [root]
        while stack:
            cur = stack.pop()
            result.append(cur.val)
            if cur.right:
                stack.append(cur.right)
            if cur.left:
                stack.append(cur.left)

        return result

Reference

• preorder traversal分析