算法训练营Day17

2023-12-15 14:38:34

110.平衡二叉树

110. 平衡二叉树 - 力扣（LeetCode）

核心：左右子树的高度不超过1

如果不是平衡二叉树，则返回-1.通过是否是-1来判断是否是平衡二叉树

求高度，采用后续遍历。

再复习一下后续遍历的思想，可以将左右子树的情况给到根节点做判断。

class Solution {
    public boolean isBalanced(TreeNode root) {
        int res = getHeight(root);
        if(res==-1) return false;
        return true;
    }
    private int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHeigh = getHeight(root.left);
        if(leftHeigh==-1) return -1;
        int rightHeigh = getHeight(root.right);
        if(rightHeigh==-1) return -1;
        int res;
        if(Math.abs(rightHeigh-leftHeigh)>1) {
            res = -1;
        }else{
            return 1+Math.max(leftHeigh,rightHeigh);
        }
        return res;
    }
}

?257.?二叉树的所有路径?(涉及回溯知识，二刷时注意)

257. 二叉树的所有路径 - 力扣（LeetCode）

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        List<Integer> paths = new ArrayList<>();
        tarversal(root,paths,result);
        return result;
    }
    private void tarversal(TreeNode root,List<Integer> paths,List<String> res){
        //前序。根
        paths.add(root.val);
        //叶子（收集）
        if(root.left==null&&root.right==null){
            StringBuilder sb = new StringBuilder();
            for(int i = 0;i<paths.size()-1;i++){
                sb.append(paths.get(i)).append("->");
            }
            sb.append(paths.get(paths.size()-1));
            res.add(sb.toString());
            return;
        }

        //左
        if(root.left!=null){
            tarversal(root.left,paths,res);
            paths.remove(paths.size()-1);//回溯
        }
        //右
        if(root.right!=null){
            tarversal(root.right,paths,res);
            paths.remove(paths.size()-1);//回溯
        }
    }


}

404.左叶子之和?

404. 左叶子之和 - 力扣（LeetCode）

注意左叶子的节点需要注意root.left.left和root.right.rihgt都为null才是叶子

就是这里后续遍历的逻辑，比卡哥的简洁一点吧，可以写到left和right后面

这个自己对比卡哥的，再体会一下。

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root==null){
            return 0;
        }
        
        int left=sumOfLeftLeaves(root.left);
        int right=sumOfLeftLeaves(root.right);
        int sum =0;
        if(root.left!=null&&root.left.left==null&&root.left.right==null){
            sum+=root.left.val;
        }    
        return sum+left+right;
    }
    
}

文章来源:https://blog.csdn.net/weixin_65728526/article/details/135012489
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。