1.二叉树

写在前面

本系列笔记主要作为笔者刷题的题解，所用的语言为Python3，若于您有助，不胜荣幸。

1.1二叉树理论基础

二叉树[binary tree]是一种非线性数据结构，代表根节点和叶子节点之间的派生关系。二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。

二叉树是存储方式有两种：分别是链式存储、顺序存储。链式存储方式就是使用指针，顺序存储方式就是使用数组。链式存储方式如下，我们可以使用如下的方式来定义一个二叉树的节点

class TreeNode:
    def __init__(self, val:int, left: Optional[TreeNode]=None, right: Optional[TreeNode]=None):
        self.val: int = val                     # 节点值
        self.left: Optional[TreeNode] = left    # 左引用
        self.right: Optional[TreeNode] = right   # 右引用

顺序存储，我们可以使用一个数组来保存二叉树中节点的值，当我们需要查询一个节点的左右子节点的值时，我们使用当前的索引i，2*i+1即左子节点的索引，2*i+2即右子节点的索引。

二叉树的常见术语：

• 根节点root node：位于二叉树顶层的节点，没有父节点
• 叶节点leaf node：没有子节点的节点，其两个指针均指向None
• 边edge：连接两个节点的线段，即节点的引用
• 边所在的层level：从顶至底递增，根节点所在的层为1
• 节点的度degree：节点的子节点数量，在二叉树中，度的取值范围为0、1、2
• 二叉树的高度height：从根节点到最远叶子节点所经过的边的数量
• 节点的深度depth：任意一个节点到根节点的距离
• 节点的高度height：任意一个节点到叶子节点的距离

在我们解题的过程中，二叉树主要有两种主要的形式：满二叉树和完全二叉树

满二叉树：如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，那么这棵二叉树就被称为满二叉树，如图所示：

完全二叉树：在完全二叉树中，除了最底层的节点可能没有填满外，其余每层节点数都达到了最大值，并且最下面一层的节点都集中在该层最左边的若干位置，若最底层为第$h$层（$h$从1开始），则该层包含$1\sim 2^{(h-1)}$个节点，如图所示：

二叉搜索树：二叉搜索树引入了数值关系，二叉搜索树是一个有序树：

• 若它的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；
• 若它的右子树不为空，则右子树上所有节点的值均大于它的根节点的值；
• 它的左，右子树也分别为二叉搜索树。

二叉搜索树其实符合一种中序遍历的方式，如图所示：

平衡二叉树：是指二叉树中任意节点的左子树和右子树的高度之差的绝对值不超过1。

平衡二叉搜索树：平衡二叉搜索树又被称为AVL（Adelson-Velsky and Landis）树，且具有以下的性质，

• 它是一棵空树或者它的左右两个子树的高度差的绝对值不超过1；
• 它的两个左右子树都是一棵平衡二叉树。

如果一棵树既是二叉搜索树又是平衡二叉树，那么它就是一棵平衡二叉搜索树，如图所示：

二叉树的遍历方式：二叉树主要有两种遍历方式

1. 深度优先遍历：先往深度走，遇到叶子节点再往回走
2. 广度优先遍历：逐层去遍历

这两种遍历方式其实是图论中的基本遍历方式，从深度优先遍历和广度优先遍历进一步拓展，则有：

• 深度优先遍历
  • 前序遍历（递归法，迭代法)
  • 中序遍历（递归法，迭代法)
  • 后序遍历（递归法，迭代法)
• 广度优先遍历
  • 层次遍历（迭代法)

前序、中序、后序遍历是一种基于深度优先的搜索方式，它体现了一种“先走到尽头，再回溯继续”的思想，通常使用递归来进行实现。

1.2二叉树的递归遍历

递归算法的三要素：

• 确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
• 确定终止条件：写完了递归算法，在运行时，经常会遇到栈溢出的错误，这就是因为我们没有确定递归的终止条件，操作系统也是用一个栈结构来保存每一层递归的信息，如果递归没有终止，那么操作系统的这个栈必然会溢出。
• 确定单层递归的逻辑：确定每一层递归需要处理的信息，在这里也就是重复调用自身来实现递归的过程。

三道题目分别是：

144. 二叉树的前序遍历

解法一：常规写法

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def recurse(cur: Optional[TreeNode], res: List[int]) -> None:       # 不直接返回结果，而使用一个数组来保存结果
            if cur==None:
                return
            res.append(cur.val)
            recurse(cur.left, res)
            recurse(cur.right, res)

        ans: List[int] = []
        recurse(root, ans)
        return ans

解法二：Pythonic

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:         # 递归直接返回结果，不使用数组来保存，
        if root == None:
            return []
        mid: List[int] = [root.val]
        left: List[int] = self.preorderTraversal(root.left)
        right: List[int] = self.preorderTraversal(root.right)
        return mid + left + right

中序遍历和后序遍历比较类似，这里就不给出所有代码了。

145. 二叉树的后序遍历

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root==None:
            return []
        mid: List[int] = [root.val]
        left: List[int] = self.postorderTraversal(root.left)
        right: List[int] = self.postorderTraversal(root.right)
        return left + right + mid

94. 二叉树的中序遍历

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root == None:
            return []
        mid: List[int] = [root.val]
        left: List[int] = self.inorderTraversal(root.left)
        right: List[int] = self.inorderTraversal(root.right)
        return left + mid + right

1.3二叉树的迭代遍历

递归的实现是：每一次递归调用都会把函数的局部变量、参数值和返回值等压入调用栈中。使用迭代来遍历二叉树，其实就是手动使用一个栈，用迭代的方式来进行遍历。

这里特别需要注意的一点是，以前序遍历为例：中左右，当我们处理完中节点的时候，我们需要再处理左节点和右节点，此时的入栈顺序应该是->右->左，因为当我们弹出的时候，这样才符合正确的前序遍历顺序->左->右。

144. 二叉树的前序遍历

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stack: List[Optional[TreeNode]] = []
        ans: List[int] = []
        stack.append(root)
        while stack:
            node: Optional[TreeNode] = stack.pop()
            if node != None:        # 中
                ans.append(node.val)
            else:
                continue
            stack.append(node.right)    # 右
            stack.append(node.left)     # 左
        return ans

145. 二叉树的后序遍历

如何从前序遍历改为后序遍历呢？前序遍历的顺序是中左右，后序遍历的顺序是左右中，我们只需要交换处理左和右的两行，最后再把结果颠倒过来就行了，右左中<->中左右

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stack: List[Optional[TreeNode]] = []
        ans: List[int] = []
        stack.append(root)
        while stack:
            node: Optional[TreeNode] = stack.pop()
            if node != None:            # 中
                ans.append(node.val)
            else:
                continue
            stack.append(node.left)     # 左
            stack.append(node.right)    # 右
        return ans[::-1]        # 颠倒结果

94. 二叉树的中序遍历

在处理二叉树的中序遍历时，我们不能够在上述代码的基础上就行修改了直接完成二叉树的中序遍历，因为我们在迭代的过程中有两个过程：

• 处理：将元素放入ans数组中
• 访问：遍历所有的节点

我们访问前序和后序遍历中节点的时候，处理和访问的节点是一致的都是中间节点，但我们进行中序遍历的时候，访问的节点和处理的节点不是一致的，所以中序遍历的代码和前序和后序遍历的不统一。

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans: List[int] = []
        stack: List[Optional[TreeNode]] = []
        cur: Optional[TreeNode] = root
        while cur != None or stack:
            # 先访问底层的左子树
            if cur != None:
                stack.append(cur)
                cur = cur.left
            # 到达最左节点后处理栈顶元素
            else:
                cur = stack.pop()
                ans.append(cur.val)
                cur = cur.right
        return ans

1.4二叉树的统一迭代法

上述我们实现二叉树的前序遍历和后序遍历的方式是较为统一的，但是如果要实现二叉树的中序遍历就不那么统一了，中序遍历完全是另一种风格了，针对上述的三种遍历方式，我们可以采用一种统一的迭代方式来进行遍历。

为了处理这种访问的元素和要处理的元素不一致的情况，那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记，这样我们就可以使用一个栈来进行三种顺序的遍历了，那么如何做标记呢？就是要处理的节点放入栈之后，紧接着放一个空指针作为标记。

144. 二叉树的前序遍历

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans: List[int] = []
        stack: List[Optional[TreeNode]] = []
        node: Optional[TreeNode] = None
        if root:                            # 对None指针进行剪枝
            stack.append(root)
        while stack:
            node = stack.pop()
            if node != None:
                if node.right:              # 右
                    stack.append(node.right)
                if node.left:               # 左
                    stack.append(node.left)
                stack.append(node)          # 中
                stack.append(None)          # 标记位
            else:
                node = stack.pop()
                ans.append(node.val)
        return ans

145. 二叉树的后序遍历

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans: List[int] = []
        stack: List[Optional[TreeNode]] = []
        node: Optional[TreeNode] = None
        if root:
            stack.append(root)
        while stack:
            node = stack.pop()
            if node != None:        
                stack.append(node)              # 中
                stack.append(None)
                if node.right != None:          
                    stack.append(node.right)    # 右
                if node.left != None:
                    stack.append(node.left)     # 左
            else:
                node = stack.pop()
                ans.append(node.val)
        return ans

94. 二叉树的中序遍历

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans: List[int] = []
        stack: List[Optional[TreeNode]] = []
        node: Optional[TreeNode] = None
        if root:
            stack.append(root)
        while stack:
            node = stack.pop()
            if node != None:
                if node.right != None:              # 右
                    stack.append(node.right)
                stack.append(node)                  # 中
                stack.append(None)
                if node.left != None:               # 左
                    stack.append(node.left)
            else:
                node = stack.pop()
                ans.append(node.val)
        return ans

1.5二叉树的层序遍历

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

思路：对于层序遍历，我们为了知道哪些节点是在同一层，我们需要使用一个队列来保存访问到的节点，并且使用一个size变量来记录当前层中的节点数量，这样我们就能进行层序遍历了。

from collections import deque
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        que: deque = deque()
        if not root:        # 避免传入空指针
            return []
        que.append(root)
        ans: List[List[int]] = []
        while que:
            size = len(que)
            res: List[int] = []
            while size:
                node: Optional[TreeNode] = que.popleft()
                res.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
                size -= 1
            ans.append(res)
        return ans

对于二叉树的层序遍历，还有十道相关的题目，这里分别列举出来：

107. 二叉树的层序遍历 II

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

思路：这道题只需要在返回的时候对结果进行一个翻转即可。

from collections import deque
class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        que: deque = deque()
        if not root:            # 避免传入空指针
            return []
        que.append(root)
        ans: List[List[int]] = []
        while que:
            size: int = len(que)
            res: List[int] = []
            while size:
                node: Optional[TreeNode] = que.popleft()
                res.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
                size -= 1
            ans.append(res)
        return ans[::-1]

199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

思路：本题的思路也是层序遍历，只不过需要我们保存右侧的视图，我们只需要保存每次层序遍历的最后一个值即可。

from collections import deque
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        que: deque = deque()
        if not root:
            return []
        ans: List[int] = []
        que.append(root)
        while que:
            size: int = len(que)
            while size:
                node: Optional[TreeNode] = que.popleft()
                if size==1:
                    ans.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
                size -= 1
        return ans

637. 二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

from collections import deque
class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        que: deque = deque()
        if not root:
            return [0]
        ans: List[float] = []
        que.append(root)
        while que:
            size: int = len(que)
            l: int = size
            s: float = 0.0
            while size:
                node: Optional[TreeNode] = que.popleft()
                s += node.val
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
                size -= 1
            ans.append(s/l)
        return ans

429. N 叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val: int = val
        self.children: List[Optional[Node]] = children

思路：N叉树的定义如上，这里的self.children的值其实是一个List存放了该节点的所有子节点的，明确这一点之后其实就和层序遍历无异了。

from collections import deque
class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root:
            return []
        que: deque = deque()
        ans: List[List[int]] = []
        que.append(root)
        while que:
            size: int = len(que)
            res: List[int] = []
            while size:
                cur: Optional[Node] = que.popleft()
                res.append(cur.val)
                for node in cur.children:
                    if node != None:
                        que.append(node)
                size -= 1
            ans.append(res)
        return ans

515. 在每个树行中找最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

from collections import deque
class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        que: deque = deque()
        ans: List[int] = []
        que.append(root)
        while que:
            size: int = len(que)
            temp: List[int] = []
            while size:
                node: Optional[TreeNode] = que.popleft()
                temp.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
                size -= 1
            ans.append(max(temp))
        return ans

116. 填充每个节点的下一个右侧节点指针

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

思路：我们在进行层序遍历的时候，只需要将前一个弹出的节点用pre进行保存，让其的next指针指向当前弹出的节点cur即可

from collections import deque
class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return root
        que: deque = deque()
        que.append(root)
        while que:
            size: int = len(que)
            pre: Optional[Node] = None
            while size:
                cur: Optional[Node] = que.popleft()
                if pre != None:
                    pre.next = cur
                if size == 1:           # 可省略，因为已经默认设置成None了
                    cur.next = None
                if cur.left != None:
                    que.append(cur.left)
                if cur.right != None:
                    que.append(cur.right)
                size -= 1
                pre = cur
        return root     # 我们修改完毕后,需要返回根节点,供系统判题

117. 填充每个节点的下一个右侧节点指针 II

给定一个二叉树：

class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

思路：这道题和上一道题不同的地方在于这道题不是完美二叉树，但对于我们使用层序遍历的方式来说并没有影响，所以，这道题可以和上一题的解法一模一样。

from collections import deque
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
        que: deque = deque()
        que.append(root)
        while que:
            size: int = len(que)
            pre: Optional[Node] = None
            while size:
                cur: Optional[Node] = que.popleft()
                if pre != None:
                    pre.next = cur
                if cur.left != None:
                    que.append(cur.left)
                if cur.right != None:
                    que.append(cur.right)
                size -= 1
                pre = cur
        return root

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

解法一：使用层序遍历

from collections import deque
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root: 
            return 0
        que: deque = deque()
        que.append(root)
        depth: int = 0
        while que:
            size: int = len(que)
            while size:
                node: Optional[TreeNode] = que.popleft()
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
                size -= 1
            depth += 1
        return depth

解法二：使用递归

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明：**叶子节点是指没有子节点的节点。

思路：需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

from collections import deque
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        que: deque = deque()
        que.append(root)
        depth: int = 0
        while que:
            depth += 1
            for _ in range(len(que)):
                node: Optional[TreeNode] = que.popleft()
                if node.left == None and node.right == None:	# 遇到叶子节点直接返回值
                    return depth
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        return depth

1.6翻转二叉树

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

解释：翻转的意思就是交换根节点下的左右子树。

解法一：采用递归

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 采用前序遍历
        if not root:
            return root
        root.left, root.right = root.right, root.left   # 中
        self.invertTree(root.left)                      # 左
        self.invertTree(root.right)                     # 右
        return root
    
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 采用后序遍历
        if not root:
            return root
        self.invertTree(root.left)                      # 左
        self.invertTree(root.right)                     # 右
        root.left, root.right = root.right, root.left   # 中
        return root
    
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 采用中序遍历
        if not root:
            return root
        self.invertTree(root.left)                      # 左
        root.left, root.right = root.right, root.left   # 中
        self.invertTree(root.left)                      # 右
        return root

解法二：采用迭代法

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 采用前序遍历
        if not root:
            return root
        stack: List[Optional[TreeNode]] = []
        stack.append(root)
        while stack:
            node: Optional[TreeNode] = stack.pop()          
            node.left, node.right = node.right, node.left   # 中
            if node.left:                                   # 左
                stack.append(node.left)
            if node.right:                                  # 右
                stack.append(node.right)
        return root

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 采用中序遍历
        if not root:
            return root
        stack: List[Optional[TreeNode]] = []
        stack.append(root)
        while stack:
            node: Optional[TreeNode] = stack.pop()          
            if node.left:                                   # 左
                stack.append(node.left)
            node.left, node.right = node.right, node.left   # 中
            if node.left:                                   # 右
                stack.append(node.left)
        return root
    
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 采用后序遍历
        if not root:
            return root
        stack: List[Optional[TreeNode]] = []
        stack.append(root)
        while stack:
            node: Optional[TreeNode] = stack.pop()          
            if node.left:                                   # 左
                stack.append(node.left)
            if node.right:                                  # 右
                stack.append(node.right)
            node.left, node.right = node.right, node.left   # 中
        return root

解法三：采用层序遍历

from collections import deque
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 前序遍历
        if not root:
            return root
        que: deque = deque()
        que.append(root)
        while que:
            for _ in range(len(que)):
                node: Optional[TreeNode] = que.popleft()
                node.left, node.right = node.right, node.left       # 中
                if node.left:
                    que.append(node.left)                           # 左
                if node.right:
                    que.append(node.right)                          # 右
        return root
    
from collections import deque
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 中序遍历
        if not root:
            return root
        que: deque = deque()
        que.append(root)
        while que:
            for _ in range(len(que)):
                node: Optional[TreeNode] = que.popleft()
                if node.left:
                    que.append(node.left)                           # 左
                node.left, node.right = node.right, node.left       # 中
                if node.left:
                    que.append(node.left)                          # 右
        return root

from collections import deque
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 后序遍历
        if not root:
            return root
        que: deque = deque()
        que.append(root)
        while que:
            for _ in range(len(que)):
                node: Optional[TreeNode] = que.popleft()
                if node.left:
                    que.append(node.left)                           # 左
                if node.right:
                    que.append(node.right)                          # 右
                node.left, node.right = node.right, node.left       # 中
        return root

1.7对称二叉树

101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

思路：这到题我们只能使用后序遍历的方式，这样我们才能收集左右子树的信息然后返回给上一个子树。当我们需要收集子节点的信息向上一层返回的时候，我们需要使用后序遍历。

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def recurse(left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
            if left != None and right == None: return False
            elif left == None and right != None: return False
            elif left == None and right == None: return True
            elif left.val != right.val: return False
            else:
                outside: bool = recurse(left.left, right.right)         # 左
                inside: bool = recurse(left.right, right.left)          # 右
                return outside and inside                               # 中
        return not root or recurse(root.left, root.right)               # 防止传入空指针

1.8二叉树的最大深度

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

• 节点的深度depth：任意一个节点到根节点的距离
• 节点的高度height：任意一个节点到叶子节点的距离

对于求取深度，我们可以使用前序遍历，对于求取高度，我们一般使用后序遍历。

解法一：递归

后序遍历求取根节点的高度，那么根节点的高度就是整棵树的最大深度。

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # 采用后序遍历
        if not root: 
            return 0
        leftheight: int = self.maxDepth(root.left)      # 左
        rightheight: int = self.maxDepth(root.right)    # 右
        height: int = 1 + max(leftheight, rightheight)  # 中
        return height

下面是后序遍历的精简写法：

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

解法二：迭代

迭代的解法，我们可以使用层序遍历来求解，我们遍历的层数，就是二叉树的最大深度

from collections import deque
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        que: deque = deque()
        que.append(root)
        depth: int = 0
        while que:
            depth += 1
            for _ in range(len(que)):
                node: Optional[TreeNode] = que.popleft()
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        return depth

559. N 叉树的最大深度

解法一：递归

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        depth: int = 1
        for node in root.children:
            depth = max(depth, self.maxDepth(node)+1)
        return depth

解法二：迭代

from collections import deque
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        que: deque = deque()
        que.append(root)
        depth: int = 0
        while que:
            depth += 1
            for _ in range(len(que)):
                node: Optional[Node] = que.popleft()
                for child in node.children:
                    if child:       # 如果child不为空指针
                        que.append(child)
        return depth

1.9二叉树的最小深度

111. 二叉树的最小深度

解法一：递归

思路：注意这里的中处理逻辑很容易写成

height: int = 1 + min(leftheight, rightheight)

这样是不行的，因为当我们的节点没有左节点或者右节点的时候，它就直接进行返回了，并不能找到正确的子节点继续遍历直到找到叶子节点。

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        # 后序遍历
        if not root:
            return 0
        leftheight: int = self.minDepth(root.left)      # 左
        rightheight: int = self.minDepth(root.right)    # 右
        if root.left != None and root.right == None:    # 中
            return 1 + leftheight
        elif root.left == None and root.right != None:
            return 1 + rightheight
        else:
            height: int = 1 + min(leftheight, rightheight)
        return height

解法二：迭代

from collections import deque
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        que: deque = deque()
        que.append(root)
        depth: int = 0
        while que:
            depth += 1
            for _ in range(len(que)):
                node: Optional[TreeNode] = que.popleft()
                if node.left == None and node.right == None:        # 遇到第一个叶子节点则返回
                    return depth
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        return depth

1.10完全二叉树的节点个数

222. 完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~2h 个节点。

可以使用普通二叉树的一些解法，包括递归和迭代之类的方法。

解法一：递归法

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        # 后序遍历
        if root == None:
            return 0
        left: int = self.countNodes(root.left)      # 左
        right: int = self.countNodes(root.right)    # 右
        count: int = left + right + 1               # 中
        return count

解法二：迭代法

from collections import deque
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        que: deque = deque()
        que.append(root)
        count: int = 0
        while que:
            for _ in range(len(que)):
                count += 1
                node: Optional[TreeNode] = que.popleft()
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        return count

除了上述的解法之外，我们还可以利用完全二叉树的特性来进行计算，完全二叉树的节点数量$n$和其层数之间$l$满足$n=2^l-1$，利用这一特性，我们可以判断一个节点的左右子节点是否为完全二叉树，如果为完全二叉树我们就直接返回其节点数量即可，这样加速了递归的过程。

解法三：利用完全二叉树的特性，丰富终止条件

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        left: Optional[TreeNode] = root.left
        leftdepth: int = 0
        while left:
            left = left.left
            leftdepth += 1
        right: Optional[TreeNode] = root.right
        rightdepth: int = 0
        while right:
            right = right.right
            rightdepth += 1
        if rightdepth == leftdepth:
            return 2**(leftdepth+1) - 1     # leftdepth计算的是该节点的子树的层数，还要再加上该节点，才算是整个完全二叉树子树的层数
        
        leftnodenums: int = self.countNodes(root.left)      # 左
        rightnodenums: int = self.countNodes(root.right)    # 右
        nodenums: int = leftnodenums + rightnodenums + 1    # 中
        return nodenums

1.11平衡二叉树

110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        # 后序遍历
        def recurse(root: Optional[TreeNode]) -> int:
            if not root:
                return 0
            leftheight: int = recurse(root.left)        # 左
            if leftheight == -1:
                return -1
            rightheight: int = recurse(root.right)      # 右
            if rightheight == -1:
                return -1
            height: int = max(leftheight, rightheight) + 1 if abs(leftheight - rightheight) <= 1 else -1    # 中
            return height
        return recurse(root) != -1

1.12二叉树的所有路径

257. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

思路：这道题其实涉及到了回溯的过程，我们在使用递归法的时候要思考怎么才能正确回溯到初始的根节点，然后再次出发。

class Solution:
    def traversal(self, cur: Optional[TreeNode], path: List[int], result: List[str]):
        path.append(cur.val)                        # 中
        if not cur.left and not cur.right:          # 到达叶子节点，则保存结果
            sPath = '->'.join(map(str, path))
            result.append(sPath)
            return 
        if cur.left:                                # 左
            self.traversal(cur.left, path, result)
            path.pop()                              # 主动回溯到上一个节点
        if cur.right:                               # 右
            self.traversal(cur.right, path, result)
            path.pop()

    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        path: List[int] = []
        result: List[str] = []
        if not root:
            return []
        self.traversal(root, path, result)
        return result

1.13左叶子之和

404. 左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。

思路：在做这道题之前，我们需要明确左叶子节点的定义。左叶子节点的定义如下，节点A的左孩子不为空，且左孩子的左右孩子都为空（说明为叶子节点），那么节点A的左孩子为左叶子节点。

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if not root:                                        # 遇到空root直接return 0
            return 0
        if root.left == None and root.right == None:        # 遇到叶子节点也return 0，现在还不能确定是否是左叶子
            return 0
        leftval: int = self.sumOfLeftLeaves(root.left)      # 左
        if root.left and root.left.right == None and root.left.left == None:        # 遇到左叶子节点
            leftval = root.left.val
        rightval: int = self.sumOfLeftLeaves(root.right)    # 右
        result: int = leftval + rightval                    # 中
        return result 

1.14找树左下角的值

513. 找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

解法一：迭代法，层序遍历

from collections import deque
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        que: deque = deque()
        que.append(root)
        result: int = 0
        while que:
            for i in range(len(que)):
                node: Optional[TreeNode] = que.popleft()
                if i == 0:			# 保存最左侧的结果
                    result = node.val
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        return result

解法二：递归法

思路：在使用递归法的时候，我们优先遍历左侧的值，无论是前序中序还是后序，这里不涉及到中间节点的处理逻辑，所以前中后序都是可以的，当我们遍历到最大深度的时候，优先查找左侧的值，如果左侧有值则直接返回即可，如果没有值说明我们应该想右侧去寻找。

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        self.max_depth: int = float('-inf')     # 定义全局变量
        self.result: int = None
        self.traversal(root, 0)
        return self.result
        
    def traversal(self, node: Optional[TreeNode], depth: int) -> None:
        if node.left == None and node.right == None:    # 终止条件，找到叶子节点
            if depth > self.max_depth:
                self.max_depth = depth
                self.result = node.val
                return
        if node.left:                           # 左
            depth += 1
            self.traversal(node.left, depth)
            depth -= 1                          # 回溯
        if node.right:                          # 右
            depth += 1
            self.traversal(node.right, depth)
            depth -= 1                          # 回溯

上述代码还可以隐藏回溯的过程做到如下的精简

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        self.max_depth: int = float('-inf')     # 定义全局变量
        self.result: int = None
        self.traversal(root, 0)
        return self.result
        
    def traversal(self, node: Optional[TreeNode], depth: int) -> None:
        if node.left == None and node.right == None:    # 终止条件，找到叶子节点
            if depth > self.max_depth:
                self.max_depth = depth
                self.result = node.val
                return
        if node.left:                           # 左
            self.traversal(node.left, depth+1)  # 回溯
        if node.right:                          # 右
            self.traversal(node.right, depth+1) # 回溯   

1.15路径总和

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

思路：这道题和257. 二叉树的所有路径的思路基本一致，都可以使用递归来求解。

class Solution:
    def traversal(self, cur: Optional[TreeNode], path: List[int], result: List[int]) -> None:
        path.append(cur.val)
        if cur.left == None and cur.right == None:        # 遇到叶子节点则找到一条完整路径
            result.append(sum(path))
            return
        if cur.left:
            self.traversal(cur.left, path, result)
            path.pop()
        if cur.right:
            self.traversal(cur.right, path, result)
            path.pop()

    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:            # 排除传入空指针
            return False
        res: List[int] = []
        path: List[int] = []
        self.traversal(root, path, res)
        return targetSum in res

上述的实现寻找了所有的路径和，这种思路比较慢，我们其实不需要找到所有的路径和，我们只需要找到一条符合题意的结果之后我们就能立刻返回了。

class Solution:
    def traversal(self, cur: Optional[TreeNode], count: int) -> bool:
        if cur.left == None and cur.right == None and count == 0:
            return True
        if cur.left == None and cur.right == None:
            return False
        if cur.left:
            count -= cur.left.val
            if self.traversal(cur.left, count):
                return True
            count += cur.left.val       # 回溯
        if cur.right:
            count -= cur.right.val
            if self.traversal(cur.right, count):
                return True
            count += cur.right.val      # 回溯
        return False

    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        return self.traversal(root, targetSum-root.val)

上述代码还可以做如下的两种精简

第一种是隐藏回溯

class Solution:
    def traversal(self, cur: Optional[TreeNode], count: int) -> bool:
        if cur.left == None and cur.right == None and count == 0:
            return True
        if cur.left == None and cur.right == None:
            return False
        if cur.left:
            if self.traversal(cur.left, count - cur.left.val): # 回溯
                return True
        if cur.right:
            if self.traversal(cur.right, count - cur.right.val): # 回溯
                return True
        return False

    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        return self.traversal(root, targetSum-root.val)

第二种是无需回溯

class Solution:
    def traversal(self, cur: Optional[TreeNode], count: int) -> bool:
        count -= cur.val                # 把处理逻辑放在这里，我们就不需要再进行回溯了
        if cur.left == None and cur.right == None and count == 0:
            return True
        if cur.left:
            if self.traversal(cur.left, count):
                return True
        if cur.right:
            if self.traversal(cur.right, count):
                return True
        return False

    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        return self.traversal(root, targetSum)

113. 路径总和 II

class Solution:
    def traversal(self, cur: Optional[TreeNode], path: List[int], result: List[List[int]], target: int):
        path.append(cur.val)
        if cur.left == None and cur.right == None:      # 遇到叶子节点
            if sum(path) == target:
                result.append(path[:])                  # 这里需要使用path的拷贝值，不能直接传入path，不然操作的是同一块内存，会被pop清空
                return
        if cur.left:
            self.traversal(cur.left, path, result, target)
            path.pop()                                  # 回溯
        if cur.right:
            self.traversal(cur.right, path, result, target)
            path.pop()                                  # 回溯

    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        if not root:
            return []
        path: List[int] = []
        res: List[List[int]] = []
        self.traversal(root, path, res, targetSum)
        return res

class Solution:
    def traversal(self, cur: Optional[TreeNode], path: List[int], result: List[List[int]], count: int) -> None:
        path.append(cur.val)
        count -= cur.val
        if cur.left == None and cur.right == None:
            if count == 0:
                result.append(path[:])
                return
        if cur.left:                                        # 左
            self.traversal(cur.left, path, result, count)
            path.pop()                                      # 回溯
        if cur.right:                                       # 右
            self.traversal(cur.right, path, result, count)
            path.pop()                                      # 回溯

    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        if not root:
            return []
        path: List[int] = []
        result: List[int] = []
        self.traversal(root, path, result, targetSum)
        return result

Reference

[1] Hello 算法
[2] 代码随想录