参考文献链接：代码随想录
本人代码是Java版本的，如有别的版本需要请上代码随想录网站查看。
110.平衡二叉树
力扣题目链接
解题思路
这道题目刚看到以为和二叉树的最大深度差不多，上来写了一堆迭代求深度的代码结果发现不对劲。
看了题解才发现高度和深度是完全不一样的。
知道高度的定义后，如何遍历数呢，那当然是后续遍历，因为后序遍历是左右中，只有知道左和右之后你才能知道中间节点的高度。所以求高度用后续，求深度的话前序即可。
代码示例
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) != -1;}public int getHeight(TreeNode node){if(node == null){return 0;}int leftHeight = 0;int rightHeight = 0;leftHeight = getHeight(node.left); if(leftHeight == -1){return -1;}rightHeight = getHeight(node.right);if(rightHeight == -1){return -1;}if(Math.abs(leftHeight - rightHeight) > 1){return -1;}else{return Math.max(leftHeight,rightHeight) + 1;}}
}
257. 二叉树的所有路径
力扣题目链接
解题思路
首先确定这道题的遍历顺序，因为题目要求是顺序的路径，那我们就得用前序遍历。然后我们还是使用递归法，一层一层去收集路径，当某个节点没有左右子树就说明到头了，收集这个路径即可。递归的时候我们要加入回溯，因为我们要收集所有路径而不是一条，所以递归后要回溯到上层，这样才能收集另一个子树的路径。
更多详细请看代码和注释
代码示例
class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> result = new ArrayList<String>();pin(root,new ArrayList<Integer>(),result);return result;}//递归参数解释，paths是每一个节点val的收集，result是每天路径的收集。public void pin(TreeNode node,List<Integer> paths,List<String> result){//为什么这次终止条件不在最上面，因为终止的时候要把val拼成路径，会漏掉该node的val值，所以要先添加。paths.add(node.val);if(node.left == null && node.right == null){//当没有左右子树就收集路径StringBuffer sb = new StringBuffer();for(int i = 0;i<paths.size()-1;i++){sb.append(paths.get(i)).append("->");}sb.append(paths.get(paths.size() - 1));result.add(sb.toString());return;}//当左子树不为null，就加入递归，递归后记得回溯。if(node.left != null){pin(node.left,paths,result);paths.remove(paths.size() - 1);}//同理if(node.right != null){pin(node.right,paths,result);paths.remove(paths.size() - 1);}}
}
404.左叶子之和
力扣题目链接
解题思路
该题目其实跟求最大深度差不多，层序遍历即可，只不过当我们添加左子树进入队列时，判断一下如果该左子树是左叶子，那就加上它的值。
代码示例
class Solution {public int sumOfLeftLeaves(TreeNode root) {int result = 0;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){int len = queue.size();while(len-- > 0){TreeNode temp = queue.poll();if(temp.left != null){//在此处判断加入的左子树是不是左叶子即可。if(temp.left.left == null && temp.left.right == null){result = result + temp.left.val;}queue.offer(temp.left);}if(temp.right != null){queue.offer(temp.right);}}}return result;}
}
222.完全二叉树的节点个数
力扣题目链接
解题思路
本题还是跟上述题目一个思路，前序遍历一直记录节点数即可。
递归法
class Solution {public int countNodes(TreeNode root) {if(root==null){return 0;}//返回左右节点长度+1 1是当前节点return countNodes(root.left)+countNodes(root.right)+1;}
}
递归法
层序遍历时每次poll的时候result++即可。
class Solution {public int countNodes(TreeNode root) {if(root==null){return 0;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int result = 0;while(!queue.isEmpty()){int size = queue.size();while(size-->0){TreeNode now = queue.poll();result++;if(now.left!=null){queue.offer(now.left);}if(now.right!=null){queue.offer(now.right);}}}return result;}
}
