代码随想录算法训练营Day13

110.平衡二叉树

力扣题目链接：. - 力扣（LeetCode）

后序迭代

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root)!=-1;
    }
    public int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftheight=getHeight(root.left);
        int rightheith=getHeight(root.right);
        if(leftheight==-1||rightheith==-1){
            return -1;
        }
        else if(Math.abs(leftheight-rightheith)>1){
          return -1;  
        }
        return Math.max(leftheight,rightheith)+1;
    }
}

257. 二叉树的所有路径

力扣题目链接：. - 力扣（LeetCode）

前序递归

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
            List<String> res=new ArrayList<>();
            if(root==null){
                return res;
            }
            List<Integer> pathnode=new ArrayList<>();
            bianli(root,res,pathnode);
            return res;
    }
    public void bianli(TreeNode root,List<String> res,List<Integer> pathnode){
        pathnode.add(root.val);
        if(root.left==null&&root.right==null){
            StringBuilder str=new StringBuilder();
            for(int i=0;i<pathnode.size()-1;i++){
                str.append(pathnode.get(i)).append("->");
            }
            str.append(pathnode.get(pathnode.size()-1));
            res.add(str.toString());
            return;
        }
        if(root.left!=null){
            bianli(root.left,res,pathnode);
            if(!pathnode.isEmpty()){
                pathnode.remove(pathnode.size()-1);
            }       
        }
        if(root.right!=null){
            bianli(root.right,res,pathnode);
            if(!pathnode.isEmpty()){
                pathnode.remove(pathnode.size()-1);
            }     
        }
        return;
    }
}

404.左叶子之和

力扣题目链接：. - 力扣（LeetCode）

后序递归

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

222.完全二叉树的节点个数

力扣题目链接：. - 力扣（LeetCode）

层序遍历

class Solution {
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        Deque<TreeNode> myque=new LinkedList<>();
        myque.offer(root);
        int sum=0;
        int res=0;
        while(!myque.isEmpty()){
            sum++;
            int len=myque.size();
            res+=len;
            if(len!=Math.pow(2,sum-1))
            break;
            while(len>0){
               TreeNode cur=myque.poll();
                if(cur.left!=null){
                    myque.offer(cur.left);
                }
                if(cur.right!=null){
                    myque.offer(cur.right);
                }
                len--;
            }
        }
        return res;
    }
}