两种典型的递归方法解决树的遍历问题

• 二叉树的最大深度

描述：给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

递归法（自顶向下）

通过递归法，左右子树同时向下递归遍历，直到遍历到最后节点，累计节点深度。返回累计的左右子树最大的深度+1，加1是为了把根节点计算进去。

class Solution:
	def maxDepth(self,root:Optional(TreeNode))->TreeNode:
		if not root:
			return 0
		# 左子树的深度
		left_dep=self.maxDepth(root.left)
		# 右子树的深度
		right_dep=self.maxDepth(root.right)
		return max(left_dep,right_dep)+1

• 对称二叉树

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

1. 递归法（自顶向下）

该方法通过“自顶向下”的递归方案执行，根据对称二叉树的定义，对于树中任意两个对称节点L和R，一定有：

• L.val = R.val，即两对称节点值相等；
• L的左子节点的值等于R的右子节点的值相等；
• L的右子节点的值等于R的左子节点的值相等；
  在代码实现的过程中，要注意递归的结束条件，首先是左右节点都为空，返回True。然后左节点或右节点为空，或左右节点值不相等，返回False。
  
  ps：图片源自leetcode

class Solution:
	def isSymmetric(self,root:Optional[TreeNode])->bool:
		def recur(L,R):
			if not L and not R:
				return True
			if not L or not R or L.val!=R.val:
				return False
			return recur(L.left,R.right) and recur(L.right,R.left)
		return not root or recur(root.left,root.right) 

2. 迭代法

迭代法通常使用队列或栈来存储需要处理的节点，对于轴对称二叉树的检查，我们可以使用一个队列来存储需要比较的节点对。每一对节点应该满足镜像对称的条件。
我们从根节点的左子节点和右子节点开始，将它们作为一对节点加入队列。然后，我们不断从队列中取出节点对，并检查它们是否满足镜像对称的条件。如果满足，我们将它们的左子节点和右子节点（如果存在）作为新的节点对加入队列。如果任何时候发现不满足条件的节点对，我们就返回 False。如果队列为空时都没有发现不满足条件的节点对，我们就返回 True。

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        # 使用 deque（双端队列）来初始化一个队列，并将根节点的左子节点和右子节点作为一对加入队列。
        queue = deque([(root.left,root.right)])
        # 遍历队列
        while queue:
            # 从队列的左侧取出一个节点对（左子节点和右子节点）
            left,right=queue.popleft()
            # 如果当前取出的左子节点和右子节点都是空的，说明当前这一层已经对称
            if not left and not right:
                continue
            
            if not left or not right or left.val!=right.val:
                return False
            # 左子树左子节点和右子树右子节点作为一对加入队列，节点为空也会加入到队列
            queue.append((left.left,right.right))
            # 左子树右子节点和右子树左子节点作为一对加入队列，节点为空也会加入到队列
            queue.append((left.right,right.left))
        return True