Consider all the leaves of a binary tree. From left to right order, the values of those leaves form a leaf value sequence._For example, in the given tree above, the leaf value sequence is(6, 7, 4, 9, 8). Two binary trees are considered_leaf-similar if their leaf value sequence is the same.Returntrueif and only if the two given trees with head nodesroot1androot2are leaf-similar.

这道题也没有太多要说的，直接找出所有leaf node，DFS或者BFS都可以，然后比较两个leaf node 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> leaves1 = getLeaves(root1);
        List<Integer> leaves2 = getLeaves(root2);

        if(leaves1.size() != leaves2.size())
            return false;

        for(int i = 0; i < leaves1.size(); i++) {
            if(leaves1.get(i) != leaves2.get(i))
                return false;
        }

        return true;
    }

    public List<Integer> getLeaves(TreeNode root) {
        List<Integer> res =  new ArrayList<Integer>();

        if(root == null)
            return res;

        dfs(res, root);
        return res;
    }

    public void dfs(List<Integer> res, TreeNode root) {
        if(root == null)
            return;

        if(root.left == null && root.right == null){
            res.add(root.val);
            return;
        }

        dfs(res, root.left);
        dfs(res, root.right);
    }
}