代码随想录第十七天 ｜ 二叉树

今天继续二叉树的学习

110. 平衡二叉树

class Solution {
    public boolean isBalanced(TreeNode root) {
        return dfs(root)>=0;
    }
    public int dfs(TreeNode root){
        if(root == null){
            return 0;
        }
        int lt = dfs(root.left);
        int rt = dfs(root.right);
        if(lt >= 0 && rt >= 0 && Math.abs(lt - rt)<=1){
            return Math.max(lt, rt)+1;
        }
        else{
            return -1;
        }
    }
}

对比root两边子树的深度差是否在1内

257. 二叉树的所有路径

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if(root==null){
            return res;
        }
        dfs(res,"",root);
        return res;
    }
    public void dfs(List<String> res,String cur, TreeNode root ){
        if(root != null){
            cur += root.val;
        }else{
            return;
        }
        
        if(root.left == null && root.right == null){
            res.add(cur);
        }
        else{
            dfs( res,cur+"->", root.left);
            dfs( res,cur+"->", root.right);
        }

    }
}

如果没有子树了，那么就把之前的路径加入res里面。不然就依次添加路径

404. 左叶子之和

class Solution {
    int res = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        
        if(root == null ){
            return res;
        }
        dfs(root);
        return res;
    }
    public void dfs( TreeNode root){
        if(root == null){
            return;
        }
        if(root.left != null&&(root.left.left==null&&root.left.right==null)){
            // System.out.println(res);
            res+=root.left.val;
        }
        dfs(root.right);
        dfs(root.left);
    }
    
}

遍历，遇到左叶子，加入到res。

一刷先掌握好递归解法吧，不用考虑栈溢出先