LeetCode872. 叶子相似的树-蒲公英云

LeetCode872. 叶子相似的树

以你之姓@ 2022-05-17 06:23 245阅读 0赞

请考虑一颗二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

举个例子，如上图所示，给定一颗叶值序列为 (6, 7, 4, 9, 8) 的树。

如果有两颗二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。

如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

提示：

给定的两颗树可能会有 1 到 100 个结点。

思路：深度优先遍历二叉树，记录下叶子结点的值；再比较两颗树的叶子结点序列是否相同。

/**
 * 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> l1=getLeaf(root1);
        List<Integer> l2=getLeaf(root2);
        if(l1.equals(l2)) {
            return true;
        }
        return false;
    }
    public  List<Integer> getLeaf(TreeNode root){
        List<Integer> list=new ArrayList<Integer>();  //存储叶子结点值
        ArrayDeque<TreeNode> stack=new ArrayDeque<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode node=stack.pop();
            if(node.left!=null) {
                stack.push(node.left);
            }
            if(node.right!=null) {
                stack.push(node.right);
            }
            if(node.left==null&&node.right==null) {
                list.add(node.val);
            }
        }
        return list;
    }
}