力扣872. 叶子相似的树-Java双百解法

请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

image

题目解法：

首先明确题意是让我们判定两颗数叶子节点序列是否相同，我们可以看到上树的叶子节点序列是(6, 7, 4, 9, 8)，所以是从左到右排列的，然后我们就直到使用深度优先遍历了，具体具体二叉树深度中序遍历的模板是：

DFS(TreeNode root){
  if(root == null){
    return;
  }else{
    DFS(root.left);      //遍历左子树
    reslult.add(root); //处理数组
    DFS(root.right);  //遍历右子树
  }
}

而对于本题，是求找到叶子节点的序列，所以我们需要处理叶子节点，而不是上面模板的现在需要处理节点root，所以我们得到如下代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
  //这里我们定义两个List用于存放结果序列
    List<Integer> list1 = new ArrayList<Integer>();
    List<Integer> list2 = new ArrayList<Integer>(); 
    public void getRoot(TreeNode root, List list){
        if(root == null){
            return;
        }
       //处理叶子节点；
        if(root.left == null && root.right == null){
            list.add(root.val);       
            return;
        }
          //遍历左右非叶子节点子树
            getRoot(root.left, list);
            getRoot(root.right, list);
    }
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        getRoot(root1, list1);
        getRoot(root2, list2);
        //判定两个List是否相同；
        if(list1.size() != list2.size()){
            return false;
        }
        for(int i = 0; i < list1.size(); i++){
            if(list1.get(i).intValue() != list2.get(i).intValue()){
                return false;
            }
        }
        return true;
    }
}

至此，这道简单题目我们已经完成了，每日一题，加油加油！

image.png