目录
一、 222 完全二叉树的节点个数
题目
题解
方法一：递归法
方法二：
二、257 二叉树的所有路径
题目
题解
方法一：递归法
方法二：回溯法
三、04 左叶子之和
题目
题解
一、 222 完全二叉树的节点个数
题目
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
提示：
树中节点的数目范围是[0, 5 * 104]
0 <= Node.val <= 5 * 104
题目数据保证输入的树是 完全二叉树题解
方法一：递归法
其实这道题的最暴力的解法就是直接用递归来统计结点的个数，根本不需要考虑什么完全二叉树还是完美二叉树，递归在手，遇 tree 不愁。直接一行搞定碉堡了，这可能是我见过最简洁的 brute force 的解法了吧。
参见代码如下：
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}
}方法二：
（1）完全二叉树是一种特殊的二叉树，具有以下特点：
- 所有层，除了最后一层，都必须完全填满。
- 在最后一层，所有的节点尽可能地向左排列。
简而言之，完全二叉树的每一层都满了，只有最后一层可以不满，但节点必须从左到右依次填入。
1 / \ 2 3 / \ / 4 5 6（2）完美二叉树（也称为满二叉树）是一种更严格的二叉树，具有以下特点：
- 所有层都必须完全填满。
- 每个内部节点都有两个子节点，且所有叶节点都在同一层。
简而言之，完美二叉树的每一层都必须是满的。
1 / \ 2 3 / \ / \ 4 5 6 7
利用一下完全二叉树这个条件，通过上面对完全二叉树跟完美二叉树的定义比较，可以看出二者的关系是，完美二叉树一定是完全二叉树，而完全二叉树不一定是完美二叉树。
那么这道题给的完全二叉树就有可能是完美二叉树，若是完美二叉树，节点个数很好求，为2的h次方减1，h为该完美二叉树的高度。若不是的话，只能老老实实的一个一个数节点了。
思路是由 root 根结点往下，分别找最靠左边和最靠右边的路径长度，如果长度相等，则证明二叉树最后一层节点是满的，是满二叉树，直接返回节点个数，如果不相等，则节点个数为左子树的节点个数加上右子树的节点个数再加1(根节点)，其中左右子树节点个数的计算可以使用递归来计算。
参见代码如下：
class Solution {
public int countNodes(TreeNode root) {
int lc = 0, rc = 0;
TreeNode l = root;
TreeNode r = root;
while(l != null){
++lc;
l = l.left;
}
while(r != null){
++rc;
r = r.right;
}
if(lc == rc) return (int)Math.pow(2, lc) - 1;
return countNodes(root.left) + countNodes(root.right) + 1;
}
}二、257 二叉树的所有路径
题目
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
提示：
树中节点的数目在范围 [1, 100] 内
-100 <= Node.val <= 100题解
方法一：递归法
这里我们使用递归的方法来获取二叉树的所有路径，在我们对树进行递归遍历时，如果当前节点是叶子节点，说明我们就找到了一条满足条件的路径，如果当前节点不是叶子节点，那么就继续递归遍历左右子树，直到遍历到叶子节点。
代码如下，
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
dfs(root,"",res);
return res;
}
private static void dfs(TreeNode root, String path, List<String> list) {
// 节点为空, 递归终止
if (root == null) return;
// 当前节点是叶子节点, 说明找到了一条路径, 加入结果列表中
if (root.left == null && root.right == null) {
list.add(path + root.val);
}
// 当前节点不是叶子节点, 则继续遍历左子树和右子树寻找路径
dfs(root.left,path + root.val + "->",list);
dfs(root.right,path + root.val + "->",list);
}
方法二：回溯法
提到根节点到叶子节点的路径，那一定就是先序遍历了。我们要拿到一条路径是很简单的，只要从根节点开始沿途一直寻找到叶子节点就可以了，本题的难点在于如何得到所有的路径。也就是当我们达到了叶子节点之后，还要回溯回去，换个方向找找还有没有其他的路径。 说到这里 —— 那么这道题就转化为一道回溯法的问题了。
- 回溯法参数 ： 当前遍历到的节点 root、 当前得到的路径 path
- 结束条件 ： 找到叶子节点，即左右子节点都为空的节点
- 单层逻辑： 在路径中加入当前节点值 root.val，判断左子节点是否为空，不为空则递归调用左节点，然后回溯。对右子节点同理。
代码如下，定义主方法 binaryTreePaths，接受一个二叉树的根节点 root 作为参数，返回从根节点到叶节点的所有路径。创建一个局部列表 path 用于存储当前路径。调用辅助方法 backTrace 开始回溯遍历二叉树。
class Solution {
public List<String> binaryTreePaths(TreeNode root){
List<String> res = new ArrayList<>(); // 存最终的结果
if(root == null) return res;
List<Integer> paths = new ArrayList<>(); // 作为结果中的路径
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){
// 输出
StringBuilder sb = new StringBuilder(); // StringBuilder用来拼接字符串，速度更快
for(int i = 0; i < paths.size() - 1; i++){
sb.append(paths.get(i)).append("->");
}
sb.append(paths.get(paths.size() - 1)); // 记录最后一个结点
res.add(sb.toString()); // 收集一个路径
return;
}
// 递归和回溯是同时进行，所以要放在同一个花括号里
if(root.left != null){ // 左
traversal(root.left, paths, res);
paths.remove(paths.size() - 1); // 回溯
}
if(root.right != null){ // 右
traversal(root.right, paths, res);
paths.remove(paths.size() - 1); // 回溯
}
}
}三、04 左叶子之和
题目
给定二叉树的根节点 root ，返回所有左叶子之和。
提示:
节点数在 [1, 1000] 范围内
-1000 <= Node.val <= 1000题解
这个题的解题思路：遍历 + 判断。
- 遍历：遍历二叉树的所有节点
- 判断：判断当前节点是否是左子节点，以及是否是叶子节点
只要一个节点满足判断中的两个条件，那么我们就可以将当前节点的节点值累加起来，如果当前节点是右子节点或者不是叶子节点，那么我们就继续递归的遍历它，就可以得到最终的答案。
大体流程如下：
- 首先， 如果根节点root为null或者只有一个节点，则说明没有叶子节点，直接返回0；
- 否则，添加一个递归方法recursive，有2个参数，分别是当前节点的左右子节点，flag为左右子节点的标识，递归过程如下：
- 调用递归方法recursive，参数分别为root的左右子节点，flag为相应的标识；
- 判断递归方法中的root如果为null，则返回；
- 如果root没有左右子节点，且flag标识为左子节点，则将root的值加到结果result中；
- 否则，递归调用recursive，参数分别为root的左右子节点，flag为相应的标识。
- 最后，返回result即为所有的左叶子节点之和。
- 调用递归方法recursive，参数分别为root的左右子节点，flag为相应的标识；
代码如下，
class Solution {
public int result = 0;
public int sumOfLeftLeaves(TreeNode root) {
if (root == null || (root.left == null && root.right == null)) return 0;
recursive(root.left, true);
recursive(root.right, false);
return result;
}
public void recursive(TreeNode root, boolean flag) {
if (root == null) return;
if (root.left == null && root.right == null && flag) result += root.val;
recursive(root.left, true);
recursive(root.right, false);
}
}
