当前位置：首页 > news >正文

比较两种判断相同二叉树的方法：递归与遍历序列对比

news 2025/5/6 6:30:46

在二叉树操作中，判断两棵树是否相同是一个常见的问题。本文将对比两种不同的解决方案：递归法和遍历序列对比法，分析它们的优缺点，并探讨为何递归法是更优的选择。

问题描述

给定两棵二叉树的根节点 p 和 q，判断它们是否在结构和节点值上完全相同。

方法一：递归法

递归法的核心思想是逐层比较节点，确保每个节点的值和结构一致。

public boolean isSameTree(TreeNode p, TreeNode q) {if (p == null && q == null) return true;else if (p == null || q == null) return false;else if (p.val != q.val) return false;return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

分析

正确性：递归法直接比较当前节点的值和结构，并递归检查左右子树。只有当所有对应节点均匹配时，才返回 true。
时间复杂度：O(n)，每个节点仅访问一次。
空间复杂度：O(h)，其中 h 为树的高度（递归栈的深度）。

方法二：遍历序列对比法

该方法通过生成两棵树的前序、中序和后序遍历序列，并比较三者是否完全一致。

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {List<Integer> arrMiddleP = new ArrayList<Integer>();List<Integer> arrMiddleQ = new ArrayList<Integer>();List<Integer> preP = new ArrayList<Integer>();List<Integer> preQ = new ArrayList<Integer>();List<Integer> afterP = new ArrayList<Integer>();List<Integer> afterQ = new ArrayList<Integer>();middle(p, arrMiddleP);middle(q, arrMiddleQ);pre(p, preP);pre(q, preQ);after(p, afterP);after(q, afterQ);if (arrMiddleP.equals(arrMiddleQ) && preP.equals(preQ)&&(afterP.equals(afterQ))) {return true;}return false;}public void middle(TreeNode x, List<Integer> arrMiddle) {if (x == null) {return;}middle(x.left, arrMiddle);arrMiddle.add(x.val);middle(x.right, arrMiddle);}public void pre(TreeNode x, List<Integer> arrPre) {if (x == null) {return;}arrPre.add(x.val);pre(x.left, arrPre);pre(x.right, arrPre);}public void after(TreeNode x, List<Integer> arrPre) {if (x == null) {return;}after(x.left, arrPre);after(x.right, arrPre);arrPre.add(x.val);}}

分析

思路：如果两棵树的前序、中序、后序遍历结果完全相同，则认为它们相同。
潜在问题：
- 结构信息丢失：遍历序列未记录 null 节点，导致不同结构的树可能生成相同的遍历序列。例如：
  - 树 A：根节点为 1，左子节点为 1。
  - 树 B：根节点为 1，右子节点为 1。
    两者的前序、中序、后序结果均为 [1, 1]，但结构不同。
- 重复值问题：当节点值重复时，遍历序列无法区分结构差异。
效率：需要三次遍历，时间和空间复杂度均为 O(n)，效率低于递归法。