二叉树的中序遍历

描述 

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3] 输出：[1,3,2] 

示例 2：

输入：root = [] 输出：[] 

示例 3：

输入：root = [1] 输出：[1] 

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

Leecode题解henry

在树的深度优先遍历中（包括前序、中序、后序遍历），递归方法最为直观易懂，但考虑到效率，我们通常不推荐使用递归。

栈迭代方法虽然提高了效率，但其嵌套循环却非常烧脑，不易理解，容易造成 “一看就懂，一写就废” 的窘况。而且对于不同的遍历顺序（前序、中序、后序），循环结构差异很大，更增加了记忆负担。

因此，使用一种 “颜色标记法” （瞎起的名字……），兼具栈迭代方法的高效，又像递归方法一样简洁易懂，更重要的是，这种方法对于前序、中序、后序遍历，能够写出完全一致的代码。

其核心思想如下：

使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
如果遇到的节点为灰色，则将节点的值输出。

使用这种方法实现的中序遍历如下：

​ # 定义二叉树节点的类 class TreeNode:     def __init__(self, val=0, left=None, right=None):         # 节点值         self.val = val         # 左子节点         self.left = left         # 右子节点         self.right = right  # 定义解决方案的类 class Solution:     def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:         # 定义颜色标记：white表示未访问，green表示已访问         white, green = 0, 1                  # 初始化结果列表，用于存储中序遍历的结果         res = []                  # 初始化栈，栈中存储的是元组（节点的颜色，节点）         stack = [(white, root)]                  # 当栈不为空时，循环处理         while stack:             # 弹出栈顶元素，获取节点的颜色和节点             color, node = stack.pop()                          # 如果节点为空，跳过本次循环             if node is None:                 continue                          # 如果节点是white色（未访问），按照右->根->左的顺序将节点入栈             if color == white:                 # 先将右子节点入栈                 stack.append((white, node.right))                 # 将当前节点标记为green色（已访问）后入栈                 stack.append((green, node))                 # 最后将左子节点入栈                 stack.append((white, node.left))             else:                 # 如果节点是green色（已访问），将节点值加入结果列表                 res.append(node.val)                  # 返回中序遍历的结果         return res  ​

整体分析

该代码通过使用颜色标记法和栈来实现二叉树的中序遍历（左-根-右），具体过程如下：

1. TreeNode类: 定义了一个简单的二叉树节点类，包含节点值、左子节点和右子节点的指针。
2. Solution类: 定义了一个解决方案类，其中包含一个用于中序遍历的方法inorderTraversal。
3. inorderTraversal方法:
   • 定义了两个颜色标记white和green，分别表示未访问和已访问。
   • 初始化一个空的结果列表res，用于存储中序遍历的结果。
   • 初始化一个栈stack，并将根节点与white标记一起放入栈中。
   • 进入while循环，循环处理栈中的节点：
     • 弹出栈顶元素，获取节点的颜色和节点本身。
     • 如果节点为空，跳过本次循环。
     • 如果节点是white（未访问），按照右->根->左的顺序将节点及其子节点入栈：
       • 先将右子节点与white标记一起放入栈中。
       • 将当前节点与green标记一起放入栈中。
       • 最后将左子节点与white标记一起放入栈中。
     • 如果节点是green（已访问），将节点值加入结果列表res。
   • 循环结束后，返回结果列表res。

 如要实现前序、后序遍历，只需要调整左右子节点的入栈顺序即可。

二叉树的最大深度

 描述

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

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

示例 1：

输入：root = [3,9,20,null,null,15,7] 输出：3 

示例 2：

输入：root = [1,null,2] 输出：2 

提示：

• 树中节点的数量在 [0, 104] 区间内。
• -100 <= Node.val <= 100

Leecode题解Krahets 

解题思路：

树的遍历方式总体分为两类：深度优先搜索（DFS）、广度优先搜索（BFS）。

常见 DFS ： 先序遍历、中序遍历、后序遍历。
常见 BFS ： 层序遍历（即按层遍历）。
求树的深度需要遍历树的所有节点，本文将介绍基于 后序遍历（DFS） 和 层序遍历（BFS） 的两种解法。

方法一：后序遍历（DFS）

树的后序遍历 / 深度优先搜索往往利用 递归 或 栈 实现，本文使用递归实现。

关键点： 此树的深度和其左（右）子树的深度之间的关系。显然，此树的深度 等于 左子树的深度 与 右子树的深度中的 最大值 +1 。

算法解析：

终止条件： 当 root​ 为空，说明已越过叶节点，因此返回 深度 0 。
递推工作： 本质上是对树做后序遍历。
计算节点 root​ 的 左子树的深度 ，即调用 maxDepth(root.left)。
计算节点 root​ 的 右子树的深度 ，即调用 maxDepth(root.right)。
返回值： 返回 此树的深度 ，即 max(maxDepth(root.left), maxDepth(root.right)) + 1。

代码实现 

class Solution:     def maxDepth(self, root: Optional[TreeNode]) -> int:         # 如果当前节点为空，返回深度0         if not root:              return 0                  # 递归计算左子树和右子树的最大深度，取两者的最大值再加1（当前节点）         return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1 

详细步骤

1. 检查当前节点是否为空:
   • 如果root为None，表示当前节点为空，此时返回0，因为空树的深度为0。
2. 递归调用:
   • 对左子树调用self.maxDepth(root.left)，计算左子树的最大深度。
   • 对右子树调用self.maxDepth(root.right)，计算右子树的最大深度。
3. 计算最大深度:
   • 使用max函数取左子树和右子树深度中的较大值。
   • 在较大值的基础上加1，表示当前节点的深度。
4. 返回结果:
   • 返回最终计算得到的最大深度。

方法二：层序遍历（BFS）

树的层序遍历 / 广度优先搜索往往利用 队列 实现。

关键点： 每遍历一层，则计数器 +1 ，直到遍历完成，则可得到树的深度。

算法解析：

特例处理： 当 root​ 为空，直接返回 深度 0 。
初始化： 队列 queue （加入根节点 root ），计数器 res = 0。
循环遍历： 当 queue 为空时跳出。
初始化一个空列表 tmp ，用于临时存储下一层节点。
遍历队列： 遍历 queue 中的各节点 node ，并将其左子节点和右子节点加入 tmp。
更新队列： 执行 queue = tmp ，将下一层节点赋值给 queue。
统计层数： 执行 res += 1 ，

代码实现 

class Solution:     def maxDepth(self, root: TreeNode) -> int:         # 如果根节点为空，返回深度0         if not root:              return 0                  # 初始化队列和结果变量         queue, res = [root], 0                  # 当队列不为空时，循环处理         while queue:             # 临时列表，用于存储当前层的所有节点的子节点             tmp = []                          # 遍历当前层的所有节点             for node in queue:                 # 如果左子节点存在，加入临时列表                 if node.left:                      tmp.append(node.left)                                  # 如果右子节点存在，加入临时列表                 if node.right:                      tmp.append(node.right)                          # 将队列更新为下一层的所有节点             queue = tmp                          # 深度加1             res += 1                  # 返回最终计算得到的深度         return res 

详细步骤

1. 基础情况:

   • 如果根节点为空（即root为None），返回深度为0。

2. 初始化队列和深度变量:

   • 初始化队列queue，将根节点放入队列。
   • 初始化结果变量res为0，用于存储计算得到的深度。

3. 广度优先搜索:

   • 使用while循环，当队列不为空时进行处理。
   • 初始化临时列表tmp，用于存储当前层的所有节点的子节点。
   • 遍历当前层的所有节点，将其左子节点和右子节点（如果存在）加入临时列表tmp。
   • 将队列queue更新为下一层的所有节点，即tmp。
   • 每遍历一层，深度变量res加1。

4. 返回结果:

   • 循环结束后，返回最终计算得到的深度res。