递归方法解决树的遍历问题

二叉树的最大深度

描述：给定一个二叉树 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