算法锦囊1：一文搞定二叉树-一一网

这是我参与更文挑战的第7天，活动详情查看：更文挑战

最近想把自己刷算法题的经验心得整理一下，一方面为了复习巩固，另一方面也希望我的分享能够帮助到更多在学习算法的朋友。

专栏名称叫《算法锦囊》，在讲解算法时会注重整体的结构性，但不会面面俱到，适合有一定算法经验的人阅读。

第一篇讲二叉树，这一部分的所有题目和源码都上传到了github的该目录下，题解用了Python和Go两种语言实现。

树，二叉树，二叉搜索树

对于链表而言，每个节点只有一个后继节点，如果有多个，就演化成了树，如果出现节点之间出现环，则演化成了有向图，特殊的，如果每个节点最多两个分支，且无环，就演化成了二叉树。

对于二叉树而言，如果每个节点仅有一个分支，则退化成了单链表。

二叉搜索树，是一种特殊的二叉树，左树所有元素的大小都小于中间节点，右树所有元素的大小都大于中间节点。

二叉树的遍历

二叉树的遍历是面试中的常考题，主要包括前序遍历，中序遍历，后序遍历和层序遍历。

前序遍历：根——左——右
中序遍历：左——根——右
后序遍历：左——右——根

记忆的时候只要记住无论是前、中、还是后，指的是根节点的遍历的位置。

接下来进入算法题实战，我这里用144. 二叉树的前序遍历作为演示。

节点定义

首先是定义树的节点。

python语言描述：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
复制代码

go语言描述：

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}
复制代码

树的遍历可以用递归法和迭代法完成。

递归法

我们首先用递归法进行实现。

python语言实现：

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

        res = []
        preorder(root)
        return res
复制代码

在preorder方法里面，灵活地调整语句的位置，可以变为中序遍历，后序遍历。

因为Python语言特性的灵活性，上面的代码也可以简化为：、

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

复制代码

补充go语言实现：

func preorderTraversal(root *TreeNode) (res []int) {
	var preorder func(node *TreeNode)
	preorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		res = append(res, node.Val)
		preorder(node.Left)
		preorder(node.Right)
	}
	preorder(root)
	return
}
复制代码

递归法的思路精髓在于，把复杂问题拆解为重复的子问题，我们只需要关注其中某一个节点该执行怎样的逻辑。

迭代法

其次是迭代法，这里要用到栈的数据结构。

Python语言实现

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        stack, res = [root], []
        while stack:
            tmp = stack.pop()
            res.append(tmp.val)
            if tmp.right:
                stack.append(tmp.right)
            if tmp.left:
                stack.append(tmp.left)
        return res
复制代码

GO语言实现

func preorderTraversal(root *TreeNode) (res []int) {
	var stack []*TreeNode
	node := root
	for node != nil || len(stack) > 0 {
		for node != nil {
			res = append(res, node.Val)
			stack = append(stack, node)
			node = node.Left
		}
		node = stack[len(stack)-1].Right
		stack = stack[:len(stack)-1]
	}
	return
}
复制代码

迭代法比较难想，需要对栈这类数据结构灵活应用，需要多看多练，理解元素入栈和出栈的时机。

层序遍历

至于层序遍历，就比较简单了，一层一层地往下遍历即可。

例题是102. 二叉树的层序遍历

因为既写go的解法又写python的解法，导致文章篇幅过长，我后面统一用python实现，其他解法可参见我的github。

python语言描述：

from collections import deque

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        res = []
        queue = deque([root])
        while queue:
            tmp = []
            for _ in range(len(queue)):
                node = queue.popleft()
                tmp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(tmp)
        return res
复制代码

层序遍历要用到队列的数据结构，在python的collections包里面

实战模拟

通过遍历，相信你大概对树的各种解法有了初步认识。

在前中后序的递归法里，又可以叫做深度优先搜索（DFS）。

在层序遍历中，引用了队列，又可以叫做广度优先搜索（BFS）。

接下来灵活应用树来来解题。

我这里限于篇幅，只找一道例题111. 二叉树的最小深度，更多题目可以看我github。

python语言描述：

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root: return 0
        if not root.left: return self.minDepth(root.right) + 1
        if not root.right: return self.minDepth(root.left) + 1
        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
复制代码