题解 | #相逆叶子# java

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root1 TreeNode类
     * @param root2 TreeNode类
     * @return bool布尔型
     */
    public boolean leafSimilar (TreeNode root1, TreeNode root2) {
        // write code here
        List<Integer> leftList = new ArrayList<>();
        List<Integer> rightList = new ArrayList<>();

        getAllLeaf(root1, leftList);
        getAllLeaf(root2, rightList);

        int lsl = leftList.size();
        int rsl = rightList.size();

        if (lsl != rsl) {
            return false;
        }

        int i = 0;
        int j = lsl - 1;
        while (i < j) {
            if (leftList.get(i) != rightList.get(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

    private void getAllLeaf(TreeNode root, List<Integer> leafList) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            leafList.add(root.val);
        }
        getAllLeaf(root.left, leafList);
        getAllLeaf(root.right, leafList);
    }
}

这道题目主要考察的是二叉树的遍历和比较。给定两棵二叉树 root1 和 root2，我们需要判断它们的叶子节点是否相似。

代码解释：

1. 首先定义了一个树节点类 TreeNode，包含节点的值 val 和指向左右子树的引用 left 和 right。
2. 在 Solution 类中，有一个 leafSimilar 方法，用于判断两棵二叉树的叶子节点是否相似。参数是两个树节点 root1 和 root2，返回值为布尔型。
3. 在方法体中，定义了两个空的列表 leftList 和 rightList，用于存储两棵树的叶子节点。
4. 调用 getAllLeaf 方法分别获取 root1 和 root2 的叶子节点，将叶子节点存入对应的列表中。
5. 获取两个列表的长度 lsl 和 rsl，如果长度不相等，说明叶子节点个数不同，直接返回 false。
6. 使用双指针技巧，初始化指针 i 为 0，指针 j 为 lsl - 1。通过循环比较 leftList[i] 和 rightList[j] 是否相等，如果不相等则返回 false。
7. 循环结束后，说明所有叶子节点都已比较完毕且相等，返回 true。
8. 定义了一个辅助方法 getAllLeaf，用于递归获取树的叶子节点。传入当前节点 root 和一个列表 leafList，如果当前节点是叶子节点（即左右子树为空），则将节点的值存入列表中。否则，递归调用 getAllLeaf 方法获取左子树和右子树的叶子节点。