二叉树常见算法题解析：结构对比、平衡性判断与右侧视图
判断两棵二叉树是否相同
给定两个二叉树的根节点 p 和 q，需要判断它们是否在结构和节点值上完全一致。若两棵树的每个对应节点都具有相同的值且子树结构一致，则认为它们是相同的。
递归解法（深度优先遍历）
采用递归方式从根节点开始逐层比较：
- 若两个节点均为空，返回
True；若仅一个为空，返回False。 - 当两者都不为空时，先比较当前节点的值，再分别递归比较左子树和右子树。
class Solution:
def isSameTree(self, root1: TreeNode, root2: TreeNode) -> bool:
if not root1 or not root2:
return root1 is root2
return (root1.val == root2.val and
self.isSameTree(root1.left, root2.left) and
self.isSameTree(root1.right, root2.right))
时间复杂度：O(n)，其中 n 是节点总数，最坏情况下需访问所有节点。
空间复杂度：O(h)，h 为树的高度，由递归调用栈深度决定。
迭代解法（广度优先遍历）
使用队列进行层序遍历，每次取出两个节点进行比对：
- 将两棵树的根节点成对入队。
- 出队后检查是否同时为空、是否有单个为空或值不匹配。
- 若通过检测，则将其左右子节点按顺序成对加入队列。
from collections import deque
class Solution:
def isSameTree(self, root1: TreeNode, root2: TreeNode) -> bool:
queue = deque([root1, root2])
while queue:
node1 = queue.popleft()
node2 = queue.popleft()
if not node1 and not node2:
continue
if not node1 or not node2 or node1.val != node2.val:
return False
queue.append(node1.left)
queue.append(node2.left)
queue.append(node1.right)
queue.append(node2.right)
return True
时间复杂度：O(n)
空间复杂度：O(w)，w 为最大宽度，队列中最多存储两层节点。
判断是否为高度平衡二叉树
一个二叉树为高度平衡，当且仅当任意节点的左右子树高度差不超过 1。
自底向上递归策略
设计辅助函数计算以某节点为根的子树高度，若发现不平衡则返回 -1 作为标记：
- 空节点高度为 0。
- 递归获取左右子树高度，任一返回 -1 则本层也返回 -1。
- 若高度差超过 1，返回 -1；否则返回子树最大高度加 1。
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def getHeight(node):
if not node:
return 0
left_h = getHeight(node.left)
if left_h == -1:
return -1
right_h = getHeight(node.right)
if right_h == -1 or abs(left_h - right_h) > 1:
return -1
return max(left_h, right_h) + 1
return getHeight(root) != -1
时间复杂度：O(n)，每个节点仅访问一次。
空间复杂度：O(h)，递归栈深度取决于树高。
获取二叉树的右侧视图
假设观察者位于树的右侧，从上往下看，只能看到每层最右边的节点。要求返回这些可见节点的值序列。
深度优先搜索（优先右子树）
利用 DFS 遍历时记录当前层级，首次到达新层时添加该节点值。由于先访问右子树，保证每层最先被记录的是最右节点。
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
result = []
def dfs(node, level):
if not node:
return
if level == len(result):
result.append(node.val)
dfs(node.right, level + 1)
dfs(node.left, level + 1)
dfs(root, 0)
return result
时间复杂度：O(n)
空间复杂度：O(h)，递归栈与结果数组合计不超过 n。
广度优先搜索（逐层处理）
按层遍历，每层只保留最后一个出队节点的值：
- 初始化队列并加入根节点。
- 每轮外循环处理一层，内循环控制当前层的所有节点。
- 当
size == 1时，表示这是该层最后一个节点，将其值加入结果列表。
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
if not root:
return []
result = []
queue = deque([root])
while queue:
size = len(queue)
for i in range(size):
current = queue.popleft()
if i == size - 1: # 当前层最后一个节点
result.append(current.val)
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
return result
时间复杂度：O(n)
空间复杂度：O(w)，队列最大容量为树的最大宽度。
