872. 叶子相似的树

题目来源

872. 叶子相似的树

题目描述

在这里插入图片描述

注意：

在这里插入图片描述

题目解析

先序遍历遍历，遇到叶结点后直接将叶结点存入数组中，那么对于两个树遍历后就分别得到两个包含叶结点的数组，最后再比较一下这两个数组是否相同即可

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null){
            return true;
        }
        if (root1 == null){
            return false;
        }
        if (root2 == null){
            return false;
        }
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        leaf(root1, list1);
        leaf(root2, list2);
        if (list1.size() != list2.size()){
            return false;
        }
        for (int i = 0; i < list1.size(); i++) {
            if (!list1.get(i).equals(list2.get(i))){
                return false;
            }
        } 
        return true;
    }
    private void leaf(TreeNode root, List<Integer> list){
        if (root.left == null && root.right == null){
            list.add(root.val);
            return;
        }
        if (root.left != null){
            leaf(root.left, list);
        }
        if (root.right != null){
            leaf(root.right, list);
        }
    }
}

在这里插入图片描述

优化：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        leaf(root1, list1);
        leaf(root2, list2);
        if (list1.size() != list2.size()){
            return false;
        }
        for (int i = 0; i < list1.size(); i++) {
            if (!list1.get(i).equals(list2.get(i))){
                return false;
            }
        }
        return true;
    }
    private void leaf(TreeNode root, List<Integer> list){
        if (root == null){
            return;
        }
        if (root.left == null && root.right == null){
            list.add(root.val);
            return;
        }
        leaf(root.left, list);
        leaf(root.right, list);
    }
}

在这里插入图片描述

可以不用数组，用两个字符串，那么在每个叶结点值直接要加上一个分隔符，这样才能保证不会错位，最后比较两个字符串是否相等即可

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        String str1 = "";
        String str2 = "";
        str1 = leaf(root1, "");
        str2 = leaf(root2, "");
        return str1.equals(str2);
    }
    private String leaf(TreeNode root, String str){
        if (root == null){
            return str;
        }
        if (root.left == null && root.right == null){
            str = str + root.val + ",";
            return str;
        }
        return  leaf(root.left, str) + leaf(root.right, str);
    }
}