day17 110

110平衡二叉树

class Solution {
    public boolean isBalanced(TreeNode root) {
        return (getHeight(root)!=-1);    //返回值是一个int 类型 左右子树的最大高度
        
    }
    public int getHeight(TreeNode root){
        if(root==null) return 0;     //1.递归终止条件 以及处理逻辑
		
        int leftlength=getHeight(root.left);  //递归单层处理逻辑
        if(leftlength==-1) return -1;
        int rightlength=getHeight(root.right);
        if(rightlength==-1) return -1;
        if(Math.abs(leftlength-rightlength)>1) return -1;
        return Math.max(leftlength-rightlength)+1;
    }
} 

二叉树的所有路径

class Solution {   //迭代法
    public List<String> binaryTreePaths(TreeNode root) {

        Stack<Object> stack=new Stack<>();
        List<String> result=new ArrayList<>();
        if(root==null){
            return result;
        }
        stack.push(root);               
        stack.push(root.val+"");    
        while(!stack.isEmpty()){
            String path = (String)stack.pop();    //利用一个栈来存遍历的节点和->,节点值
            TreeNode node=(TreeNode)stack.pop();
            if(node.left==null&&node.right==null){   //当遇到根节点，则遍历完一条路 ，则path加入result
                result.add(path);
            }
            
            if(node.right!=null){
                stack.push(node.right);
                stack.push(path+"->"+node.right.val);
            }
            if(node.left!=null){       //如果不是根节点 将他的左孩子或者右孩子先存入栈里
                stack.push(node.left);
                stack.push(path+"->"+node.left.val); //path包含当前节点的元素值
            }
        }
        return result;
    }
}

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

    }
    private void traversal(TreeNode root,List<Integer> paths,List<String> res){
        paths.add(root.val);
        if(root.left==null&&root.right==null){    //1：确定终止条件：当遇到叶子节点时结束
            StringBuilder sb=new StringBuilder();  //终止同时  的操作：   把paths里面保存的放入stringbuilder 加上箭头，组成一条路径
            for(int i=0;i<paths.size();i++){
                sb.append(paths.get(i));
                if(i!=paths.size()-1){
                    sb.append("->");
                }               
            }
            res.add(sb.toString());   //最后把这条路 加到res中
            return;                     //2：返回的就是res数组
        }

        if(root.left!=null){                //3：确定本次递归应该做什么
            traversal(root.left,paths,res);    //这一级的递归  应该做的是：递归左孩子和右孩子
            paths.remove(paths.size()-1);          //但是因为是求所有的路劲  所以  在递归左右孩子时候要回溯
        }
        if(root.right!=null){
            traversal(root.right,paths,res);
            paths.remove(paths.size()-1);
        }
    }
}

404 左叶子之和

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        int sum=0;
        
        return addLeft(root);
    }
    public int  addLeft(TreeNode root){
        if(root==null) return 0; //1：终止条件
        int sum=0;
        int sumAll=0;
        int sumLeft=0;
        int sumright=0;
        if(root.left!=null) sumLeft=addLeft(root.left);   //2本次递归操作逻辑
        if(root.right!=null) sumright=addLeft(root.right);
        if(root.left!=null&&root.left.left==null&&root.left.right==null){// 左孩子是叶子节点  则保存sum
            sum=root.left.val;
        }
        sumAll=sum+sumLeft+sumright;
        return sumAll;               //3返回值
    }
}