Binary Tree Preorder Traversal

Question

• leetcode: Binary Tree Preorder Traversal | LeetCode OJ
• lintcode: (66) Binary Tree Preorder Traversal

Problem Statement

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

Example

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

1
 \
  2
 /
3

return [1,2,3].

Challenge

Can you do it without recursion?

题解1 - 递归

面试时不推荐递归这种做法。

递归版很好理解，首先判断当前节点(根节点)是否为null，是则返回空vector，否则先返回当前节点的值，然后对当前节点的左节点递归，最后对当前节点的右节点递归。递归时对返回结果的处理方式不同可进一步细分为遍历和分治两种方法。

Python - Divide and Conquer

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        this.val = val
        this.left, this.right = None, None
"""


class Solution:
    """
    @param root: The root of binary tree.
    @return: Preorder in ArrayList which contains node values.
    """
    def preorderTraversal(self, root):
        if root == None:
            return []
        return [root.val] + self.preorderTraversal(root.left) \
                          + self.preorderTraversal(root.right)

源码分析

使用遍历的方法保存递归返回结果需要使用辅助递归函数traverse，将结果作为参数传入递归函数中，传值时注意应使用vector的引用。 分治方法首先分开计算各结果，最后合并到最终结果中。 C++ 中由于是使用vector, 将新的vector插入另一vector不能再使用push_back, 而应该使用insert。 Java 中使用addAll方法.

复杂度分析

遍历树中节点，时间复杂度 $$O(n)$$, 未使用额外空间。

题解2 - 迭代

迭代时需要利用栈来保存遍历到的节点，纸上画图分析后发现应首先进行出栈抛出当前节点，保存当前节点的值，随后将右、左节点分别入栈(注意入栈顺序，先右后左)，迭代到其为叶子节点(NULL)为止。

Python

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

class Solution:
    # @param {TreeNode} root
    # @return {integer[]}
    def preorderTraversal(self, root):
        if root is None:
            return []

        result = []
        s = []
        s.append(root)
        while s:
            root = s.pop()
            result.append(root.val)
            if root.right is not None:
                s.append(root.right)
            if root.left is not None:
                s.append(root.left)

        return result

• reference

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

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def iterative_preorder(self, root, list):
        stack = []
        while root or stack:
            if root:
                list.append(root.val)
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                root = root.right
        return list

    def recursive_preorder(self, root, list):
        if root:
            list.append(root.val)
            self.preorder(root.left,list)
            self.preorder(root.right,list)

    def preorderTraversal(self,root):
        list = []
        self.iterative_preorder(root,list)
        return list

• reference

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        this.val = val
        this.left, this.right = None, None
"""
class Solution:
    """
    @param root: The root of binary tree.
    @return: Preorder in list which contains node values.
    """
    def preorderTraversal(self, root):
        if root is None:
            return []
        stack = [root]
        preorder = []
        while stack:
            node = stack.pop()
            preorder.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return preorder

源码分析

1. 对root进行异常处理
2. 将root压入栈
3. 循环终止条件为栈s为空，所有元素均已处理完
4. 访问当前栈顶元素(首先取出栈顶元素，随后pop掉栈顶元素)并存入最终结果
5. 将右、左节点分别压入栈内，以便取元素时为先左后右。
6. 返回最终结果

其中步骤4,5,6为迭代的核心，对应前序遍历「根左右」。

所以说到底，使用迭代，只不过是另外一种形式的递归。使用递归的思想去理解遍历问题会容易理解许多。

复杂度分析

使用辅助栈，最坏情况下栈空间与节点数相等，空间复杂度近似为 $$O(n)$$, 对每个节点遍历一次，时间复杂度近似为 $$O(n)$$.