LeetCode872. 叶子相似的树

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

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

![tree.png][]

举个例子，如上图所示，给定一颗叶值序列为 `(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;
        }
    }

[tree.png]: /images/20220517/3213b0815cf4413098e42e3a28cb6d6e.png