代码随想录day17|平衡二叉树 二叉树的所有路径 左叶子之和

标签：paths right return 随想录 day17 二叉树 null root left

左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。

分析 后序遍历 因为需要先处理完子节点 返回结果给父节点

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root==null) return 0;
        return back(root);
    }

    private int back(TreeNode root){
        if(root==null) return 0;

        int left=back(root.left);
        int right=back(root.right);

        int res=0;
        if(root.left!=null&&root.left.left==null&&root.left.right==null){
            res+=root.left.val;
        }
        return res+left+right;
    }
}

二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

分析 用回溯法 前序遍历, 进入下一层时 paths.add(root.left/right.val), 返回上一层时 paths.remove(paths.size()-1) 当遇到叶子结点 (左右子节点为空的节点) 时  将paths add到res

class Solution {
    List<String> res= new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        if(root==null) return res;
        List<Integer> paths=new ArrayList<>();
        traversal(root,paths);
        return res;
    }

    private void traversal(TreeNode root, List<Integer> paths){
        if(root!=null){
                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){
            traversal(root.left,paths);
            paths.remove(paths.size()-1);
        }

        if(root.right!=null){
            traversal(root.right,paths);
            paths.remove(paths.size()-1);
        }
    }
    }
}

平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

分析 高度只能从下到上去查，所以只能后序遍历（左右中）

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        return getHight(root)!=-1;
    }

    public int getHight(TreeNode root){
        if(root==null) return 0;

        int left=getHight(root.left);
        if(left==-1){
            return left;
        }
        int right= getHight(root.right);
        if(right==-1){
            return right;
        }
        right++;
        left++;
        if(Math.abs(left-right)>1) return -1;

        return Math.max(left,right);

    }
}

 

标签：paths,right,return,随想录,day17,二叉树,null,root,left
From： https://www.cnblogs.com/Liu5419/p/17177073.html