企业官网建设流程全解析

网站建设销售话术文本格式,wordpress ux theme,wordpress去谷歌,信息技术 网站建设教案叶子相似的树 问题描述 给定两棵二叉树 root1 和 root2#xff0c;如果两棵树的叶子节点值序列相同#xff0c;则认为它们是叶子相似的。 叶子节点#xff1a;没有子节点的节点。 叶子序列#xff1a;按照从左到右的顺序遍历得到的叶子节点值组成的序列。 返回 true 如果两…叶子相似的树问题描述给定两棵二叉树root1和root2如果两棵树的叶子节点值序列相同则认为它们是叶子相似的。叶子节点没有子节点的节点。叶子序列按照从左到右的顺序遍历得到的叶子节点值组成的序列。返回true如果两棵树叶子相似否则返回false。示例输入:root1[3,5,1,6,2,9,8,null,null,7,4]root2[3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]输出:true解释:两棵树的叶子序列都是[6,7,4,9,8]输入:root1[1,2,3]root2[1,3,2]输出:false解释:root1的叶子序列是[2,3]root2的叶子序列是[3,2]算法思路深度优先搜索获取叶子序列获取叶子序列对每棵树进行深度优先遍历中序、前序、后序都可以当遇到叶子节点左右子节点都为 null时将其值加入序列保证遍历顺序是从左到右比较序列比较两棵树的叶子序列是否完全相同可以逐个比较也可以直接比较整个序列优化提前终止不需要获取完整的两个序列再比较可以同时遍历两棵树逐个比较叶子节点一旦发现不匹配就立即返回 false代码实现方法一获取完整叶子序列后比较importjava.util.*;// 二叉树节点定义classTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(){}TreeNode(intval){this.valval;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.valval;this.leftleft;this.rightright;}}classSolution{/** * 判断两棵二叉树是否叶子相似 * * param root1 第一棵树的根节点 * param root2 第二棵树的根节点 * return 如果叶子序列相同返回true否则返回false * * 算法思路 * 1. 分别获取两棵树的叶子序列 * 2. 比较两个序列是否相同 */publicbooleanleafSimilar(TreeNoderoot1,TreeNoderoot2){ListIntegerleaves1newArrayList();ListIntegerleaves2newArrayList();// 获取第一棵树的叶子序列getLeaves(root1,leaves1);// 获取第二棵树的叶子序列getLeaves(root2,leaves2);// 比较两个序列是否相同returnleaves1.equals(leaves2);}/** * 通过深度优先搜索获取树的叶子序列 * * param node 当前节点 * param leaves 存储叶子值的列表 */privatevoidgetLeaves(TreeNodenode,ListIntegerleaves){// 空节点直接返回if(nodenull){return;}// 叶子节点左右子节点都为nullif(node.leftnullnode.rightnull){leaves.add(node.val);return;}// 递归遍历左子树getLeaves(node.left,leaves);// 递归遍历右子树getLeaves(node.right,leaves);}}方法二迭代DFS获取叶子序列classSolution{/** * 使用迭代DFS获取叶子序列 */publicbooleanleafSimilar(TreeNoderoot1,TreeNoderoot2){ListIntegerleaves1getLeavesIterative(root1);ListIntegerleaves2getLeavesIterative(root2);returnleaves1.equals(leaves2);}/** * 迭代方式获取叶子序列使用栈 */privateListIntegergetLeavesIterative(TreeNoderoot){ListIntegerleavesnewArrayList();if(rootnull){returnleaves;}StackTreeNodestacknewStack();stack.push(root);while(!stack.isEmpty()){TreeNodenodestack.pop();// 叶子节点if(node.leftnullnode.rightnull){leaves.add(node.val);}// 先压入右子节点再压入左子节点// 左子节点会先被处理保证从左到右的顺序if(node.right!null){stack.push(node.right);}if(node.left!null){stack.push(node.left);}}returnleaves;}}算法分析时间复杂度O(T1 T2)T1 和 T2 分别是两棵树的节点数需要遍历每棵树的所有节点一次空间复杂度方法一递归DFSO(T1 T2 H1 H2)存储叶子序列O(L1 L2) L1、L2 是叶子节点数递归栈空间O(H1 H2)其中 H1、H2 是树的高度方法二迭代DFSO(L1 L2 H1 H2)显式栈空间代替递归栈算法过程1叶子相似的树root1: 3 root2: 3 / \ / \ 5 1 5 1 / \ / \ / \ / \ 6 2 9 8 6 7 4 2 / \ / \ 7 4 9 8 叶子序列获取过程root1 - 从根3开始遍历左子树5 - 从5遍历左子树6 → 叶子节点添加6 - 从5遍历右子树2 - 从2遍历左子树7 → 叶子节点添加7 - 从2遍历右子树4 → 叶子节点添加4 - 回到根3遍历右子树1 - 从1遍历左子树9 → 叶子节点添加9 - 从1遍历右子树8 → 叶子节点添加8 叶子序列[6, 7, 4, 9, 8] root2的叶子序列也是[6, 7, 4, 9, 8]所以返回true2叶子不相似的树root1: 1 root2: 1 / \ / \ 2 3 3 2 root1叶子序列[2, 3] root2叶子序列[3, 2] 序列不同返回false测试用例importjava.util.*;publicclassTest{// 根据数组创建二叉树publicstaticTreeNodecreateTree(Integer[]arr){if(arrnull||arr.length0||arr[0]null){returnnull;}TreeNoderootnewTreeNode(arr[0]);QueueTreeNodequeuenewLinkedList();queue.offer(root);inti1;while(!queue.isEmpty()iarr.length){TreeNodenodequeue.poll();if(iarr.lengtharr[i]!null){node.leftnewTreeNode(arr[i]);queue.offer(node.left);}i;if(iarr.lengtharr[i]!null){node.rightnewTreeNode(arr[i]);queue.offer(node.right);}i;}returnroot;}publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例1叶子相似Integer[]tree1_1{3,5,1,6,2,9,8,null,null,7,4};Integer[]tree1_2{3,5,1,6,7,4,2,null,null,null,null,null,null,9,8};TreeNoderoot1_1createTree(tree1_1);TreeNoderoot1_2createTree(tree1_2);System.out.println(Test 1: solution.leafSimilar(root1_1,root1_2));// true// 测试用例2叶子不相似Integer[]tree2_1{1,2,3};Integer[]tree2_2{1,3,2};TreeNoderoot2_1createTree(tree2_1);TreeNoderoot2_2createTree(tree2_2);System.out.println(Test 2: solution.leafSimilar(root2_1,root2_2));// false// 测试用例3单节点树TreeNoderoot3_1newTreeNode(1);TreeNoderoot3_2newTreeNode(1);System.out.println(Test 3: solution.leafSimilar(root3_1,root3_2));// true// 测试用例4单节点但值不同TreeNoderoot4_1newTreeNode(1);TreeNoderoot4_2newTreeNode(2);System.out.println(Test 4: solution.leafSimilar(root4_1,root4_2));// false// 测试用例5空树System.out.println(Test 5: solution.leafSimilar(null,null));// true// 测试用例6一个空一个非空TreeNoderoot6newTreeNode(1);System.out.println(Test 6: solution.leafSimilar(root6,null));// false// 测试用例7复杂树Integer[]tree7_1{1,2,3,4,5,6,7};Integer[]tree7_2{1,3,2,7,6,5,4};TreeNoderoot7_1createTree(tree7_1);TreeNoderoot7_2createTree(tree7_2);System.out.println(Test 7: solution.leafSimilar(root7_1,root7_2));// false// root7_1叶子: [4,5,6,7], root7_2叶子: [7,6,5,4]// 测试用例8只有右子树Integer[]tree8_1{1,null,2,null,3};Integer[]tree8_2{1,null,2,null,3};TreeNoderoot8_1createTree(tree8_1);TreeNoderoot8_2createTree(tree8_2);System.out.println(Test 8: solution.leafSimilar(root8_1,root8_2));// true}}关键点遍历顺序保证从左到右的顺序获取叶子节点DFS的递归顺序先左后右叶子节点叶子节点 左子节点为null 且 右子节点为null不能只判断其中一个子节点边界情况处理空树叶子序列为空单节点树该节点就是叶子节点一个空一个非空肯定不相似常见问题为什么不用BFSBFS也能获取叶子节点需要额外判断节点是否为叶子DFS更自然地按照从左到右的顺序访问叶子节点