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

算法题叶子相似的树

news 2026/6/10 16:16:51

叶子相似的树

问题描述

给定两棵二叉树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.val=val;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.val=val;this.left=left;this.right=right;}}classSolution{/** * 判断两棵二叉树是否叶子相似 * * @param root1 第一棵树的根节点 * @param root2 第二棵树的根节点 * @return 如果叶子序列相同返回true，否则返回false * * 算法思路： * 1. 分别获取两棵树的叶子序列 * 2. 比较两个序列是否相同 */publicbooleanleafSimilar(TreeNoderoot1,TreeNoderoot2){List<Integer>leaves1=newArrayList<>();List<Integer>leaves2=newArrayList<>();// 获取第一棵树的叶子序列getLeaves(root1,leaves1);// 获取第二棵树的叶子序列getLeaves(root2,leaves2);// 比较两个序列是否相同returnleaves1.equals(leaves2);}/** * 通过深度优先搜索获取树的叶子序列 * * @param node 当前节点 * @param leaves 存储叶子值的列表 */privatevoidgetLeaves(TreeNodenode,List<Integer>leaves){// 空节点直接返回if(node==null){return;}// 叶子节点：左右子节点都为nullif(node.left==null&&node.right==null){leaves.add(node.val);return;}// 递归遍历左子树getLeaves(node.left,leaves);// 递归遍历右子树getLeaves(node.right,leaves);}}

方法二：迭代DFS获取叶子序列

classSolution{/** * 使用迭代DFS获取叶子序列 */publicbooleanleafSimilar(TreeNoderoot1,TreeNoderoot2){List<Integer>leaves1=getLeavesIterative(root1);List<Integer>leaves2=getLeavesIterative(root2);returnleaves1.equals(leaves2);}/** * 迭代方式获取叶子序列（使用栈） */privateList<Integer>getLeavesIterative(TreeNoderoot){List<Integer>leaves=newArrayList<>();if(root==null){returnleaves;}Stack<TreeNode>stack=newStack<>();stack.push(root);while(!stack.isEmpty()){TreeNodenode=stack.pop();// 叶子节点if(node.left==null&&node.right==null){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 分别是两棵树的节点数
- 需要遍历每棵树的所有节点一次
空间复杂度：
- 方法一（递归DFS）：O(T1 + T2 + H1 + H2)
  - 存储叶子序列：O(L1 + L2)， L1、L2 是叶子节点数
  - 递归栈空间：O(H1 + H2)，其中 H1、H2 是树的高度
- 方法二（迭代DFS）：O(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]，所以返回true

2：叶子不相似的树

root1: 1 root2: 1 / \ / \ 2 3 3 2 root1叶子序列：[2, 3] root2叶子序列：[3, 2] 序列不同，返回false

测试用例

importjava.util.*;publicclassTest{// 根据数组创建二叉树publicstaticTreeNodecreateTree(Integer[]arr){if(arr==null||arr.length==0||arr[0]==null){returnnull;}TreeNoderoot=newTreeNode(arr[0]);Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);inti=1;while(!queue.isEmpty()&&i<arr.length){TreeNodenode=queue.poll();if(i<arr.length&&arr[i]!=null){node.left=newTreeNode(arr[i]);queue.offer(node.left);}i++;if(i<arr.length&&arr[i]!=null){node.right=newTreeNode(arr[i]);queue.offer(node.right);}i++;}returnroot;}publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例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_1=createTree(tree1_1);TreeNoderoot1_2=createTree(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_1=createTree(tree2_1);TreeNoderoot2_2=createTree(tree2_2);System.out.println("Test 2: "+solution.leafSimilar(root2_1,root2_2));// false// 测试用例3：单节点树TreeNoderoot3_1=newTreeNode(1);TreeNoderoot3_2=newTreeNode(1);System.out.println("Test 3: "+solution.leafSimilar(root3_1,root3_2));// true// 测试用例4：单节点但值不同TreeNoderoot4_1=newTreeNode(1);TreeNoderoot4_2=newTreeNode(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：一个空一个非空TreeNoderoot6=newTreeNode(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_1=createTree(tree7_1);TreeNoderoot7_2=createTree(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_1=createTree(tree8_1);TreeNoderoot8_2=createTree(tree8_2);System.out.println("Test 8: "+solution.leafSimilar(root8_1,root8_2));// true}}