算法题 翻转等价二叉树

951. 翻转等价二叉树

问题描述

我们可以对二叉树的任意节点进行翻转操作：交换该节点的左右子树。

如果可以通过一系列翻转操作使得二叉树root1变成root2，则称这两棵树是翻转等价的。

给定两棵二叉树的根节点root1和root2，如果它们是翻转等价的，返回true；否则返回false。

示例：

输入: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7] 输出: true 解释: 我们可以翻转root1中值为1、3和5的节点，使两棵树相等。 输入: root1 = [], root2 = [] 输出: true 输入: root1 = [], root2 = [1] 输出: false

算法思路

递归比较：

核心思想：

• 两棵树翻转等价的条件：
  1. 两棵树都为空 → 等价
  2. 一棵为空，另一棵不为空 → 不等价
  3. 两棵树根节点值不同 → 不等价
  4. 两棵树根节点值相同，且满足以下任一条件：
     • 左子树与左子树等价且右子树与右子树等价（不翻转）
     • 左子树与右子树等价且右子树与左子树等价（翻转）

代码实现

方法一：递归比较

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */classSolution{/** * 判断两棵二叉树是否翻转等价 * * @param root1 第一棵二叉树的根节点 * @param root2 第二棵二叉树的根节点 * @return 如果两棵树翻转等价返回true，否则返回false */publicbooleanflipEquiv(TreeNoderoot1,TreeNoderoot2){// 基础情况：两棵树都为空if(root1==null&&root2==null){returntrue;}// 一棵为空，另一棵不为空if(root1==null||root2==null){returnfalse;}// 根节点值不同if(root1.val!=root2.val){returnfalse;}// 递归检查两种情况：// 1. 不翻转：左子树对左子树，右子树对右子树// 2. 翻转：左子树对右子树，右子树对左子树return(flipEquiv(root1.left,root2.left)&&flipEquiv(root1.right,root2.right))||(flipEquiv(root1.left,root2.right)&&flipEquiv(root1.right,root2.left));}}

方法二：提前剪枝

classSolution{/** * 添加更多边界条件检查 */publicbooleanflipEquiv(TreeNoderoot1,TreeNoderoot2){// 都为空if(root1==null&&root2==null){returntrue;}// 一个为空if(root1==null||root2==null){returnfalse;}// 值不同if(root1.val!=root2.val){returnfalse;}// 都是叶子节点if(root1.left==null&&root1.right==null&&root2.left==null&&root2.right==null){returntrue;}// 递归检查return(flipEquiv(root1.left,root2.left)&&flipEquiv(root1.right,root2.right))||(flipEquiv(root1.left,root2.right)&&flipEquiv(root1.right,root2.left));}}

方法三：迭代

importjava.util.Stack;classSolution{/** * 使用栈模拟递归 */publicbooleanflipEquiv(TreeNoderoot1,TreeNoderoot2){Stack<TreeNode[]>stack=newStack<>();stack.push(newTreeNode[]{root1,root2});while(!stack.isEmpty()){TreeNode[]pair=stack.pop();TreeNodenode1=pair[0];TreeNodenode2=pair[1];// 都为空if(node1==null&&node2==null){continue;}// 一个为空或值不同if(node1==null||node2==null||node1.val!=node2.val){returnfalse;}// 检查子树匹配情况booleannormalMatch=(node1.left==null?node2.left==null:(node2.left!=null&&node1.left.val==node2.left.val));if(normalMatch){// 正常匹配：左对左，右对右stack.push(newTreeNode[]{node1.left,node2.left});stack.push(newTreeNode[]{node1.right,node2.right});}else{// 翻转匹配：左对右，右对左stack.push(newTreeNode[]{node1.left,node2.right});stack.push(newTreeNode[]{node1.right,node2.left});}}returntrue;}}

算法分析

• 时间复杂度：O(min(N1, N2))
  • N1 和 N2 分别是两棵树的节点数
  • 最坏情况下需要遍历所有节点
• 空间复杂度：
  • 递归：O(min(H1, H2))，H1和H2是树的高度（递归栈深度）
  • 迭代：O(min(H1, H2))，栈空间

算法过程

输入：root1 = [1,2,3,4,5,6,null,null,null,7,8],root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]

1. 根节点(1,1)：值相同，检查子树
2. 检查子树组合：
   • 正常匹配：root1.left=2vsroot2.left=3→ 值不同
   • 翻转匹配：root1.left=2vsroot2.right=2，root1.right=3vsroot2.left=3
3. 递归处理(2,2)：
   • 正常匹配：4 vs 4，5 vs 5
   • 继续递归到叶子节点
4. 递归处理(3,3)：
   • 正常匹配：6 vs 6，null vs null
5. 最终结果：所有节点都匹配，返回true

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 创建树节点TreeNodecreateNode(intval){returnnewTreeNode(val);}// 测试用例1：标准示例TreeNoderoot1_1=newTreeNode(1);root1_1.left=newTreeNode(2);root1_1.right=newTreeNode(3);root1_1.left.left=newTreeNode(4);root1_1.left.right=newTreeNode(5);root1_1.right.left=newTreeNode(6);root1_1.left.right.left=newTreeNode(7);root1_1.left.right.right=newTreeNode(8);TreeNoderoot2_1=newTreeNode(1);root2_1.left=newTreeNode(3);root2_1.right=newTreeNode(2);root2_1.left.right=newTreeNode(6);root2_1.right.left=newTreeNode(4);root2_1.right.right=newTreeNode(5);root2_1.right.right.right=newTreeNode(7);root2_1.right.right.left=newTreeNode(8);System.out.println("Test 1: "+solution.flipEquiv(root1_1,root2_1));// true// 测试用例2：空树System.out.println("Test 2: "+solution.flipEquiv(null,null));// true// 测试用例3：一个空一个非空TreeNodesingle=newTreeNode(1);System.out.println("Test 3: "+solution.flipEquiv(null,single));// falseSystem.out.println("Test 3b: "+solution.flipEquiv(single,null));// false// 测试用例4：单节点相同TreeNodenode1=newTreeNode(5);TreeNodenode2=newTreeNode(5);System.out.println("Test 4: "+solution.flipEquiv(node1,node2));// true// 测试用例5：单节点不同TreeNodenode3=newTreeNode(5);TreeNodenode4=newTreeNode(6);System.out.println("Test 5: "+solution.flipEquiv(node3,node4));// false// 测试用例6：完全相同的树TreeNodesame1=newTreeNode(1);same1.left=newTreeNode(2);same1.right=newTreeNode(3);TreeNodesame2=newTreeNode(1);same2.left=newTreeNode(2);same2.right=newTreeNode(3);System.out.println("Test 6: "+solution.flipEquiv(same1,same2));// true// 测试用例7：需要翻转的简单情况TreeNodeflip1=newTreeNode(1);flip1.left=newTreeNode(2);flip1.right=newTreeNode(3);TreeNodeflip2=newTreeNode(1);flip2.left=newTreeNode(3);flip2.right=newTreeNode(2);System.out.println("Test 7: "+solution.flipEquiv(flip1,flip2));// true// 测试用例8：复杂的不等价情况TreeNodediff1=newTreeNode(1);diff1.left=newTreeNode(2);diff1.right=newTreeNode(3);TreeNodediff2=newTreeNode(1);diff2.left=newTreeNode(2);diff2.right=newTreeNode(4);// 值不同System.out.println("Test 8: "+solution.flipEquiv(diff1,diff2));// false// 测试用例9：结构不同TreeNodestruct1=newTreeNode(1);struct1.left=newTreeNode(2);TreeNodestruct2=newTreeNode(1);struct2.right=newTreeNode(2);System.out.println("Test 9: "+solution.flipEquiv(struct1,struct2));// true (可以通过翻转)}

关键点

1. 递归：

   • 每个节点都有两种匹配方式：正常或翻转
   • 只要有一种方式能让整棵树匹配就返回true

2. 边界条件处理：

   • 空树
   • 节点值不同
   • 结构不同

3. 翻转：

   • 翻转操作可以应用在任意节点上
   • 不需要实际执行翻转，只需要验证是否存在翻转序列

常见问题

1. 为什么不需要考虑多次翻转同一个节点？
   • 翻转两次等于没有翻转，所以每个节点最多翻转一次