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;}
}