# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        res = max(left, right) + 1
        return res

复杂度

时间复杂度：$O(n)$
空间复杂度：$O(n)$

100. 相同的树

https://leetcode-cn.com/problems/same-tree/

题目描述

Note

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1： 输入: p = [1,2,3], q = [1,2,3]
输出 true

示例 2： 输入: p = [1,2], q = [1,null,2]
输出: false

思路

运用递归
关注根节点 root
然后向下递归 left 和 right

代码

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not (p or q): 
            return True
        elif not (p and q): 
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

复杂度

时间复杂度：$O(n)$
空间复杂度：$O(n)$

129. 求根到叶子节点数字之和

https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/

题目描述

Note

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

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

示例 1:
输入: [1,2,3]

    1
   / \
  2   3

输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.

思路

DFS 深度优先搜索
- 递归
- 遇到 叶节点，加入 self.res
- 否则，进行数学进位运算
BFS 深度优先搜索
- 使用双端队列，queue.popleft() 时间复杂度是 $O(1)$
- 遇到 叶节点，加入 res
- 否则，进行数学进位运算

代码

Python DFS

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        ## DFS
        def dfs(root, sum_):
            if not (root.left or root.right):
                self.res += sum_
                return
            if root.left:
                dfs(root.left, sum_*10 + root.left.val)
            if root.right:
                dfs(root.right, sum_*10 + root.right.val)
        if not root: return 0
        self.res = 0
        dfs(root, root.val)
        return self.res

Python BFS

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        ## BFS
        if not root: return 0
        res, queue = 0, collections.deque()
        queue.append((root, root.val))
        while queue:
            node, sum_ = queue.popleft()
            if not (node.left or node.right):
                res += sum_
            if node.left:
                queue.append((node.left, sum_*10 + node.left.val))
            if node.right:
                queue.append((node.right, sum_*10 + node.right.val))
        return res

复杂度

时间复杂度：$O(n)$
空间复杂度：$O(n)$ # 最坏情况，二叉数退化为单链表

513. 找树左下角的值

https://leetcode-cn.com/problems/find-bottom-left-tree-value/

题目描述

Note

给定一个二叉树，在树的最后一行找到最左边的值。

示例 1:

输入:

    2
   / \
  1   3

输出:
1

示例 2:

注意: 您可以假设树（即给定的根节点）不为 NULL。

思路

DFS 深度优先搜索
- 借助递归
- 初始化 self.res = [root.val, 0]
- 到达 叶子节点：
  - 若 self.res[1] < k，更新 self.res = [node.val, k]
  - 否则，return
- 否则，向左或向右递归
BFS 0 广度优先搜索
- 对剑指 Offer 32 - III. 从上到下打印二叉树 III 作小改动
BFS 1 广度优先搜索
- 借助双端队列
- 每层 由右向左 遍历
- 最后一个 node 即为所求

代码

Python DFS

class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        ## DFS
        def dfs(node, k):
            if not (node.left or node.right):
                if self.res[1] < k:
                    self.res = [node.val, k]
                return
            if node.left:  dfs(node.left, k+1)  # 向左递归
            if node.right: dfs(node.right, k+1) # 向右递归
        self.res = [root.val, 0]
        dfs(root, 0)
        return self.res[0]

Python BFS 0

class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        ## BFS 0
        res, queue = [], collections.deque()
        queue.append((root, 0))
        while queue:
            node, k = queue.popleft()
            if k >= len(res): res.append([])
            res[k].append(node.val)
            if node.left:
                queue.append((node.left, k+1))
            if node.right:
                queue.append((node.right, k+1))
        return res[-1][0]

Python BFS 1

class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        ## BFS 1
        queue = collections.deque()
        queue.append(root)
        while queue:
            node = queue.popleft()
            if node.right:
                queue.append(node.right)
            if node.left:
                queue.append(node.left)
        return node.val

复杂度

时间复杂度：$O(n)$
空间复杂度：$O(n)$

297. 二叉树的序列化与反序列化

https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree

题目描述

Note

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例 1： 输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

示例 2： 输入：root = []
输出：[]

思路

将 None 补充为 X

DFS
- 序列化：处理根节点，将子树交给递归
- 反序列化：构建二叉树
BFS
- 序列化：常规双端队列
- 反序列化：
  - data: 序列化节点列表（包含X）
  - queue: 层序存储非空节点

代码

Python DFS

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

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        :type root: TreeNode
        :rtype: str
        """
        if not root: return 'X'
        return str(root.val) + ',' + self.serialize(root.left) + ',' + self.serialize(root.right)
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        data = collections.deque(data.split(','))
        root = self.buildTree(data)
        return root

    
    def buildTree(self, data):
        val = data.popleft()
        if val == 'X': return None
        node = TreeNode(val)
        node.left  = self.buildTree(data)
        node.right = self.buildTree(data)
        return node
        

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

Python BFS

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

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        :type root: TreeNode
        :rtype: str
        """
        if not root: return []
        res, queue = '', collections.deque()
        queue.append(root)
        while queue:
            node = queue.popleft()
            if not node:
                res += 'X,'
            else:
                res += str(node.val) + ','
                queue.append(node.left)
                queue.append(node.right)
        return res
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        if not data: return None
        data = collections.deque(data.split(','))
        root = TreeNode(data.popleft())
        queue = collections.deque()
        queue.append(root)
        while queue:
            node = queue.popleft()
            if data:
                val = data.popleft()
                if val != 'X':
                    node.left = TreeNode(val)
                    queue.append(node.left)
            if data:
                val = data.popleft()
                if val != 'X':
                    node.right = TreeNode(val)
                    queue.append(node.right)
        return root
        

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

复杂度

时间复杂度：$O(n)$
空间复杂度：$O(n)$

987. 二叉树的垂序遍历

https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree/

题目描述

Note

给你二叉树的根结点 root ，请你设计算法计算二叉树的垂序遍历序列。

对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0)。

二叉树的垂序遍历从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。

返回二叉树的垂序遍历序列。

示例:

输入: root = [1,2,3,4,6,5,7]
输出: [[4],[2],[1,5,6],[3],[7]]
解释：
这个示例实际上与示例 2 完全相同，只是结点 5 和 6 在树中的位置发生了交换。
因为 5 和 6 的位置仍然相同，所以答案保持不变，仍然按值从小到大排序。

提示：

树中结点数目总数在范围 [1, 1000] 内
0 <= Node.val <= 1000

思路

构建字典
- key: col
- value: [row, node.val]
对字典两次排序输出
- 首先, 对 列标 col 排序
- 然后, 对二维数组 [[row, node.val], ... ,[row*, node*.val]] 的 row 和 val 依次排序
- 以上都用 sorted() 实现
DFS 深度优先搜索
- 递归实现
BFS 广度优先搜索
- 双端列表实现

代码

Python DFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:     
        vertical = collections.defaultdict(list)
        def dfs(node,row=0,col=0):
            if node is None: return None
            dfs(node.left  ,row+1,col-1)
            dfs(node.right ,row+1,col+1)
            vertical[col].append([row, node.val])    
        dfs(root)
        return [ [node_value for row_value, node_value in sorted(values) ] for col_value, values  in sorted(vertical.items()) ]

Python BFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:     
        queue, vertical = collections.deque(), collections.defaultdict(list)
        queue.append((root, 0, 0))
        while queue:
            node, row, col = queue.popleft()
            vertical[col].append([row, node.val])
            if node.left:
                queue.append((node.left, row+1, col-1))
            if node.right:
                queue.append((node.right, row+1, col+1))

        return [ [node_value for row_value, node_value in sorted(values) ] for col_value, values  in sorted(vertical.items()) ]

复杂度

时间复杂度：$O(n)$
空间复杂度：$O(n)$

扩展

剑指 offer

链接在这里 🔗

树

目录

每日一题

104. 二叉树的最大深度

题目描述

思路

代码

复杂度

100. 相同的树

题目描述

思路

代码

复杂度

129. 求根到叶子节点数字之和

题目描述

思路

代码

复杂度

513. 找树左下角的值

题目描述

思路

代码

复杂度

297. 二叉树的序列化与反序列化

题目描述

思路

代码

复杂度

987. 二叉树的垂序遍历

题目描述

思路

代码

复杂度

扩展

剑指 offer