企业官网建设流程全解析

哪些网站可以做外链,有什么平台做网站比较好,wordpress怎么开启多站点,网站开发 技术维护951. 翻转等价二叉树 问题描述 我们可以对二叉树的任意节点进行翻转操作#xff1a;交换该节点的左右子树。 如果可以通过一系列翻转操作使得二叉树 root1 变成 root2#xff0c;则称这两棵树是翻转等价的。 给定两棵二叉树的根节点 root1 和 root2#xff0c;如果它们是翻转…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算法思路递归比较核心思想两棵树翻转等价的条件两棵树都为空 → 等价一棵为空另一棵不为空 → 不等价两棵树根节点值不同 → 不等价两棵树根节点值相同且满足以下任一条件左子树与左子树等价且右子树与右子树等价不翻转左子树与右子树等价且右子树与左子树等价翻转代码实现方法一递归比较/** * 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(root1nullroot2null){returntrue;}// 一棵为空另一棵不为空if(root1null||root2null){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(root1nullroot2null){returntrue;}// 一个为空if(root1null||root2null){returnfalse;}// 值不同if(root1.val!root2.val){returnfalse;}// 都是叶子节点if(root1.leftnullroot1.rightnullroot2.leftnullroot2.rightnull){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){StackTreeNode[]stacknewStack();stack.push(newTreeNode[]{root1,root2});while(!stack.isEmpty()){TreeNode[]pairstack.pop();TreeNodenode1pair[0];TreeNodenode2pair[1];// 都为空if(node1nullnode2null){continue;}// 一个为空或值不同if(node1null||node2null||node1.val!node2.val){returnfalse;}// 检查子树匹配情况booleannormalMatch(node1.leftnull?node2.leftnull:(node2.left!nullnode1.left.valnode2.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)值相同检查子树检查子树组合正常匹配root1.left2vsroot2.left3→ 值不同翻转匹配root1.left2vsroot2.right2root1.right3vsroot2.left3递归处理(2,2)正常匹配4 vs 45 vs 5继续递归到叶子节点递归处理(3,3)正常匹配6 vs 6null vs null最终结果所有节点都匹配返回true测试用例publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 创建树节点TreeNodecreateNode(intval){returnnewTreeNode(val);}// 测试用例1标准示例TreeNoderoot1_1newTreeNode(1);root1_1.leftnewTreeNode(2);root1_1.rightnewTreeNode(3);root1_1.left.leftnewTreeNode(4);root1_1.left.rightnewTreeNode(5);root1_1.right.leftnewTreeNode(6);root1_1.left.right.leftnewTreeNode(7);root1_1.left.right.rightnewTreeNode(8);TreeNoderoot2_1newTreeNode(1);root2_1.leftnewTreeNode(3);root2_1.rightnewTreeNode(2);root2_1.left.rightnewTreeNode(6);root2_1.right.leftnewTreeNode(4);root2_1.right.rightnewTreeNode(5);root2_1.right.right.rightnewTreeNode(7);root2_1.right.right.leftnewTreeNode(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一个空一个非空TreeNodesinglenewTreeNode(1);System.out.println(Test 3: solution.flipEquiv(null,single));// falseSystem.out.println(Test 3b: solution.flipEquiv(single,null));// false// 测试用例4单节点相同TreeNodenode1newTreeNode(5);TreeNodenode2newTreeNode(5);System.out.println(Test 4: solution.flipEquiv(node1,node2));// true// 测试用例5单节点不同TreeNodenode3newTreeNode(5);TreeNodenode4newTreeNode(6);System.out.println(Test 5: solution.flipEquiv(node3,node4));// false// 测试用例6完全相同的树TreeNodesame1newTreeNode(1);same1.leftnewTreeNode(2);same1.rightnewTreeNode(3);TreeNodesame2newTreeNode(1);same2.leftnewTreeNode(2);same2.rightnewTreeNode(3);System.out.println(Test 6: solution.flipEquiv(same1,same2));// true// 测试用例7需要翻转的简单情况TreeNodeflip1newTreeNode(1);flip1.leftnewTreeNode(2);flip1.rightnewTreeNode(3);TreeNodeflip2newTreeNode(1);flip2.leftnewTreeNode(3);flip2.rightnewTreeNode(2);System.out.println(Test 7: solution.flipEquiv(flip1,flip2));// true// 测试用例8复杂的不等价情况TreeNodediff1newTreeNode(1);diff1.leftnewTreeNode(2);diff1.rightnewTreeNode(3);TreeNodediff2newTreeNode(1);diff2.leftnewTreeNode(2);diff2.rightnewTreeNode(4);// 值不同System.out.println(Test 8: solution.flipEquiv(diff1,diff2));// false// 测试用例9结构不同TreeNodestruct1newTreeNode(1);struct1.leftnewTreeNode(2);TreeNodestruct2newTreeNode(1);struct2.rightnewTreeNode(2);System.out.println(Test 9: solution.flipEquiv(struct1,struct2));// true (可以通过翻转)}关键点递归每个节点都有两种匹配方式正常或翻转只要有一种方式能让整棵树匹配就返回true边界条件处理空树节点值不同结构不同翻转翻转操作可以应用在任意节点上不需要实际执行翻转只需要验证是否存在翻转序列常见问题为什么不需要考虑多次翻转同一个节点翻转两次等于没有翻转所以每个节点最多翻转一次