代码随想录算法训练营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;}
}