LeetCode-Java-872. Leaf-Similar Trees

题目

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.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.



Note:

Both of the given trees will have between 1 and 100 nodes.

代码

简单的遍历一遍树存储其叶子节点，最后进行比较即可，注意对两个树遍历的时候方法要一致。

/**
 * 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) {
        int[] s1 = list(root1);
        int[] s2 = list(root2);
        int len1 = s1.length;
        int len2 = s2.length;

        if(len1!=len2){
            return false;
        }else{
            for(int i=0;i<len1;i++){
                    if(s1[i]!=s2[i]){
                        return false;
                    }   
            }
        }
        return true;
    }
    public static int[] list(TreeNode root){
        int [] result = new int[100];
        int len = 0;
        TreeNode cur = root;
        LinkedList<TreeNode> sqn = new LinkedList<TreeNode>();
        sqn.addFirst(root);
        while(sqn.size()!=0){
            TreeNode t = sqn.removeFirst();
            if(t.right!=null){
                sqn.addFirst(t.right);
            }
            if(t.left==null&&t.right==null){
                result[len++] = t.val;
            }
            if(t.left!=null){
                sqn.addFirst(t.left);
            }

        }
        return Arrays.copyOf(result,len);
    }
}