leetcode no.144 二叉树的前序遍历

如何在leetcode上刷题
本题题解
总结

时间过得真快，明年的这个时候就要开始找工作了，所以该做的准备还是趁早开始比较好。之后一年的时间中，将会记录每天在刷题过程中学习到的知识。

如何在leetcode上刷题

由于这是这个系列的第一篇文章，因此大概记录一下leetcode上代码的运行原理。

以No.144为例，首先在编辑器中会有如下代码：

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

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:

这是什么意思呢？实际上leetcode隐藏了对Solution.preorderTraversal()的调用过程，上面的注释说明了TreeNode类的定义也已完成并隐藏，因此我们只需要将preorderTraversal()补充完整即可，不需要自己定义代码运行的入口等等。这里我们可以看到对preorderTraversal()的root参数进行了类型的限定，返回值也被限制成List。这是我们可以利用的提示。

本题说明了输入为[1,null,2,3]，期望得到的输出为[1,2,3]，root是preorderTraversal()的参数，我们可以事先打印类型为TreeNode的root的各个属性，以便我们了解root是如何被后台生成、定义的。

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

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        print(root.val)
        print(root.left)
        print(root.right)

1
None
TreeNode{val: 2, left: TreeNode{val: 3, left: None, right: None}, right: None}

这样我们面对一个新的题目时就不会一筹莫展了。

本题题解

递归算法

递归算法是解决二叉树遍历问题最简单的方法。但是效率相对较低。这是本题最基础的解法。

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        result=[root.val]
        if root.left:
            left=self.preorderTraversal(root.left)
            result=result+left
        if root.right:
            right=self.preorderTraversal(root.right)
            result=result+right
        return result

甚至可以简化为：

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        return [root.val]+self.preorderTraversal(root.left)+self.preorderTraversal(root.right)

这种方法就不需要过多解释了。二叉树遍历的递归实现，每个结点只需遍历一次，故时间复杂度为O(n)。而使用了递归，最差情况下递归调用的深度为O(n)，所以空间复杂度为O(n)。

迭代算法（使用栈）

这个方法是本题的进阶解法，相对效率较高，但是使用了栈。

算法复杂度:

时间复杂度：访问每个节点恰好一次，时间复杂度为 O(N) ，其中 N 是节点的个数，也就是树的大小。

空间复杂度：取决于树的结构，最坏情况存储整棵树，因此空间复杂度是 O(N)。

class Solution:
    def preorderTraversal(self, root: TreeNode) -> 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

这里利用了栈的先入后出的特性，从根节点开始，每次迭代弹出当前栈顶元素，并将其孩子节点压入栈中，先压右孩子再压左孩子。输出到最终结果的顺序按照 Top->Bottom 和 Left->Right，符合前序遍历的顺序。

迭代算法（不使用栈，莫里斯遍历）

这是本题最精妙的解法，方法基于莫里斯的文章，可以优化空间复杂度。算法不会使用额外空间，只需要保存最终的输出结果。如果实时输出结果，那么空间复杂度是 O(1)。

算法的思想是，利用当前节点（node）的中序遍历前驱节点，得到前序遍历的结果。具体的方法是，从根节点（node=root）开始，先向左孩子前进一步（predecessor=node.left），再向右孩子前进n步(predecessor=predecessor.right)，直到到达叶子节点（当前节点的中序遍历的前驱节点）。将该叶子节点的右孩子设置为当前节点（predecessor.right=node），当前节点向其左孩子移动（node=node.left），若当前节点的左孩子为None，输出node.val，当前节点移动至右孩子(node=node.right)。当不断前进的步的右孩子为当前节点（predecessor.right=node）时，应当删除他们之间的虚拟连线（predecessor.right=None），当前节点向其右孩子移动（node=node.right）。直到某个当前节点的左右孩子都为None时，算法结束。

总结起来，就是4个条件分支：

1.node == None -> end
2.node.left == None -> output, node = node.right
3.precedessor.right == None -> output, precedessor.right = node, node = node.left
4.precedessor.right == node -> precedessor.right == None, node = node.right

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        node = root
        result = []
        while node:
            if not node.left:
                result.append(node.val)
                node = node.right
            else:
                pre = node.left
                
                while pre.right and pre.right is not node:
                    pre=pre.right
                    
                if not pre.right:
                    result.append(node.val)
                    pre.right = node
                    node = node.left
                elif pre.right == node:
                    pre.right = None
                    node = node.right
                    
        return result

总结

二叉树遍历的问题理论上使用递归算法是最容易理解的。如果一定要使用非递归算法，推荐使用借助栈进行数据暂存的方法，莫里斯遍历虽然巧妙，但是实在不便理解。

ac酱

完成于2019-09-01 下午

参考资料

二叉树的前序遍历-官方题解