872. Leaf-Similar Trees - Easy

前往題目

想法

• 走訪所有leaf並記錄下來，最後比較

思路

1. DFS遇到leaf放入list，走訪兩棵樹
2. 比較是否兩個list順序一致

Code

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        ArrayList<Integer> val1List = new ArrayList();
        ArrayList<Integer> val2List = new ArrayList();

        findLeaves(root1, val1List);
        findLeaves(root2, val2List);

        // Check length
        if (val1List.size() != val2List.size()) {
            return false;
        }

        // Check elements
        for (int i = 0; i < val1List.size(); ++i) {
            if (!val1List.get(i).equals(val2List.get(i))) {
                return false;
            }
        }

        return true;
    }

    private void findLeaves(TreeNode node, ArrayList<Integer> list) {
        if (node == null) return;

        if (node.left == null && node.right == null) {
            list.add(node.val);
        }

        findLeaves(node.left, list);
        findLeaves(node.right, list);
    }
}