Tree-Easy

Abstract： 更新部分Easy难度 Tree相关题解

965. Univalued Binary Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

解法一：递归遍历

记录根节点的值，逐一向下遍历即可

class Solution {
    public boolean isUnivalTree(TreeNode root) {
        if(root==null){return true;}//注意这里要判空一次，否则root.val会报空指针
        return isUnival(root,root.val);
    }
    public boolean isUnival(TreeNode root,int val){
        if(root==null){return true;}
        if(root.val!=val){return false;}
        return isUnival(root.left,val) && isUnival(root.right,val); //左右都true才是true
    }
}

112. Path Sum

解法一： DFS

DFS的核心三步：

1. 终止条件：root==null的时候返回什么？
2. 处理过程：对root和root.val 如何处理？
3. 递归条件：对左右子树如何处理？

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null){return false;}  //为空时返回false,考虑空树和空子树的情况可以得到这个结论
        sum-=root.val; //减去当前val
        if(root.left==null && root.right==null){ //为叶子节点时，要判断是不是满足条件
            if(sum==0){return true;}
            else return false;
        }
        return hasPathSum(root.left,sum) || hasPathSum(root.right,sum); 
        //左右子树一方满足即可
    }
}

100. Same Tree

解法一：递归法

1. 判空，分两种情况，两者都为空和只有一者为空
2. 比值，对比值是否相等
3. 递归，递归左右子树的结果，取**&&**

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q==null){return true;} //如果都为空，视为相等
        if(p==null || q==null){return false;} //如果一方为空，显然是不等
        if(p.val!=q.val){return false;} //比较val
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right); //递归左右子树
    }
}

解法二：迭代法(没搞懂，以后再看)

class Solution {
	public boolean check(TreeNode p,TreeNode q){
        if(p==null && q==null){return true;} //如果都为空，视为相等
        if(p==null || q==null){return false;} //如果一方为空，显然是不等
        if(p.val!=q.val){return false;} //比较val
        return true;
    }
    
    public boolean isSameTree(TreeNode p,TreeNode q){
        if(!check(p,q)){return false;}
        //下面没写完
    }
}

111. Minimum Depth of Binary Tree

解法一：递归遍历

1. 判空：空时为0

2. 判断是否为叶子节点：如果是返回1

3. 判断是否有一边为null：如果只有一边为null的话，应该对其忽略不计，否则会把此处错误地当做最小深度

4. 递归：最小深度为左右子树的最小深度中更小的那者再+1

class Solution {
    public int minDepth(TreeNode root) {
        if(root==null){return 0;} //判空
        if(root.left==null && root.right==null){return 1;} //对叶子节点的处理
        if(root.left==null || root.right==null){ //如果只有一方为空要忽略处理，这里用的是max的方法
            return Math.max(1+minDepth(root.left),1+minDepth(root.right));}
        return 1+Math.min(minDepth(root.left),minDepth(root.right)); //递归的最小值+1即为结果
    }
}

257. Binary Tree Paths

解法一： 标准DFS

没啥可说的，标准DFS不会剁手

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        return TreePaths(root,"",new ArrayList<String>());
    }

    public List<String> TreePaths(TreeNode root,String path,List<String> paths){
        if(root!=null){ //判空，为空不加入
            path+=root.val; //先拼val
            if(root.left==null&root.right==null){ //如果是叶子节点，那么add path
                paths.add(path);
            }
            else{ //否则继续递归，拼上 '->'
                path+="->";
                TreePaths(root.left,path,paths);
                TreePaths(root.right,path,paths);
            }
        }
        return paths; //返回结果
    }
}