Day15–二叉树–222. 完全二叉树的节点个数，110. 平衡二叉树，257. 二叉树的所有路径，404. 左叶子之和
本篇文章，基本上每道题目都给出了2-3篇题解。每道题写之前思考几个问题：
- 是前序遍历还是后序遍历？
- 是递归还是迭代好？
- 是先判断null再进入递归好，还是先进入递归后判断null好？
222. 完全二叉树的节点个数
思路参考自：完全二叉树的节点数，你真的会算吗？
参考二：《代码随想录》：
完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢？
在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。
思路：
完全二叉树，它的左右子树，其中至少有一颗是满二叉树。满二叉树直接根据公式计算，另一颗按照普通二叉树计算。
// 完全二叉树，它的左右子树，其中至少有一颗是满二叉树。
// 满二叉树直接根据公式计算，另一颗按照普通二叉树计算。
// 对于“不是满二叉树”的那颗子树，往下遍历的时候，也可能会有“满二叉树”的情况
// 本代码优化的速度就在于，凡是“满二叉树”就套公式。
class Solution {
public int countNodes(TreeNode root) {
// 其实这种就一句话的函数，是可以直接写在调用方法里的。
// 多写一个方法是因为，这里的节点叫root，容易误解。叫node容易理解。
return getNodeNum(root);
}
private int getNodeNum(TreeNode node) {
// 基本上所有代码就是为了“判断是否是满二叉树”
if(node==null){
return 0;
}
// 分左右子树
TreeNode left = node.left;
TreeNode right = node.right;
// 记录左右子树的高度
// 初始化为1是因为，判断左右子树是否高度相等，是在cur本节点判断的
// 如果成立，证明从本节点开始就是满二叉树，要加上本层
int leftHeight = 1;
int rightHeight = 1;
// 统计高度
while (left != null) {
left = left.left;
leftHeight++;
}
while (right != null) {
right = right.right;
rightHeight++;
}
// 如果左右子树高度相同，是一颗满二叉树，可以直接根据公式计算
if (leftHeight == rightHeight) {
return (int) Math.pow(2, leftHeight) - 1;
}
// 如果不是满二叉树，则按照普通二叉树的逻辑计算
return countNodes(node.left) + countNodes(node.right) + 1;
}
}
思路：
递归法：完全当成普通二叉树来算
class Solution {
public int countNodes(TreeNode root) {
return getNodesNum(root);
}
private int getNodesNum(TreeNode node) {
// 节点为空，返回0
if (node == null) {
return 0;
}
// 递归左子树
int leftNum = getNodesNum(node.left);
// 递归右子树
int rightNum = getNodesNum(node.right);
// 子树节点+1（自身）->返回给上一层
int curNum = leftNum + rightNum + 1;
return curNum;
}
}
110. 平衡二叉树
《代码随想录》：使用前序求深度，使用后序求高度。
思路：
- 后序遍历法：自底向上统计
- 如果高度差大于1，返回-1做标记给上层
- 每一层算高度的时候：取左右子树之中的max，然后+1，当做是本层的高度（因为高度是自底向上算的）
// 后序遍历法：自底向上统计
class Solution {
public boolean isBalanced(TreeNode root) {
return getHeight(root) == -1 ? false : true;
}
private int getHeight(TreeNode node) {
if (node == null) {
return 0;
}
int leftHeight = getHeight(node.left);
int rightHeight = getHeight(node.right);
// 如果下层返回的有-1，直接返回-1给上层
if (leftHeight == -1 || rightHeight == -1) {
return -1;
}
// 如果高度差大于1，返回-1做标记给上层
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
// 取左右子树之中的max，然后+1，当做是本层的高度（因为高度是自底向上算的）
return Math.max(leftHeight, rightHeight) + 1;
}
}
257. 二叉树的所有路径
- 方法一
思路：
后序遍历：自下而上传递字符串，把孩子传上的字符串拼接本层，加工后传给上一层
// 后序遍历：自下而上传递字符串，把孩子传上的字符串拼接本层，加工后传给上一层
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
return getChildrenString(root);
}
private List<String> getChildrenString(TreeNode node) {
List<String> list = new ArrayList<>();
if (node == null) {
return list;
}
// 拼接左节点传上来的字符串
if (node.left != null) {
List<String> leftList = getChildrenString(node.left);
// 每一个字符串，都要加上本节点的val和"->"
// 然后重新加到本节点的list里，每一个node都会新一个list
for (String s : leftList) {
String temp = node.val + "->" + s;
list.add(temp);
}
}
// 拼接右节点传上来的字符串
if (node.right != null) {
List<String> rightList = getChildrenString(node.right);
for (String s : rightList) {
String temp = node.val + "->" + s;
list.add(temp);
}
}
// 如果是叶子节点，直接返回本节点的val的字符串形式
if (node.left == null && node.right == null) {
list.add("" + node.val);
}
return list;
}
}
记录：自己写的，每一次调用都要传List<String>而且还要for循环拼接，消耗大。
- 方法二
思路：
优化后，每层的操作只是拼一次字符串
前序遍历，自顶向下传递本层拼好的字符串，到叶子节点就“结算”，添加进结果集
// 前序遍历，自顶向下传递本层拼好的字符串，到叶子节点就“结算”，添加进结果集
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
// 结果集,要作为参数传递
List<String> res = new ArrayList<>();
getPaths(root, "", res);
return res;
}
public void getPaths(TreeNode node, String s, List<String> res) {
// 处理current本节点
if (node == null) {
return;
}
// 当是叶子节点的时候，“结算”
if (node.left == null && node.right == null) {
res.add(s + node.val);
return;
}
// 非叶子节点，加上本层val加"->"传递给下一层
String ss = new StringBuilder(s).append(node.val).append("->").toString();
// 下一层
getPaths(node.left, ss, res);
getPaths(node.right, ss, res);
}
}
- 方法三
思路：
这个方法，其实也可以再加一个List<Integer>参数，每层只传递数字，到叶子节点，再一次性拼接字符串。
优点：结果的时候再用StringBuilder一次性拼接，开销小。
// 前序遍历，自顶向下传递路径上的节点的paths列表，到叶子节点就“结算”拼接字符串，添加进结果集
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
// 结果集
List<String> res = new ArrayList<>();
// 当前路径上的节点值
List<Integer> paths = new ArrayList<>();
// 开始遍历
getPaths(root, paths, res);
return res;
}
public void getPaths(TreeNode node, List<Integer> paths, List<String> res) {
// 递归终止条件：如果当前节点为null，直接返回（空节点不处理）
if (node == null) {
return;
}
// 前序遍历：先处理当前节点，将其值加入路径
paths.add(node.val);
// 当是叶子节点的时候，“结算”
if (node.left == null && node.right == null) {
// 使用StringBuilder效率更高
StringBuilder sb = new 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());
} else {
// 非叶子节点：递归遍历左子树
getPaths(node.left, paths, res);
// 递归遍历右子树
getPaths(node.right, paths, res);
}
// 回溯操作：无论当前节点是否为叶子节点，
// 在处理完所有子节点后，都要将当前节点从路径中移除
// 保证回溯到父节点时，路径信息正确
paths.remove(paths.size() - 1);
}
}
- 方法四
引自《代码随想录》
思路：
迭代法，前序遍历
特点：Stack中的泛型是<Object>，把它当成了“方法调用的栈来用”，其实就是方法调用时候的“形参列表”
// 迭代法，前序遍历
// 特点：Stack中的泛型是<Object>，把它当成了“方法调用的栈来用”，其实就是方法调用时候的“形参列表”
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
if (root == null) {
return res;
}
Deque<Object> stack = new ArrayDeque<>();
// 节点和路径同时入栈
stack.push(root);
stack.push(root.val + "");
while (!stack.isEmpty()) {
// 节点和路径同时出栈
String paths = (String) stack.pop();
TreeNode node = (TreeNode) stack.pop();
// 若找到叶子节点
if (node.left == null && node.right == null) {
res.add(paths);
}
//右子节点不为空
if (node.right != null) {
stack.push(node.right);
stack.push(paths + "->" + node.right.val);
}
//左子节点不为空
if (node.left != null) {
stack.push(node.left);
stack.push(paths + "->" + node.left.val);
}
}
return res;
}
}
404. 左叶子之和
《代码随想录》：判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。
思路：
递归遍历。要保证node.left是个叶子，才要它的值。
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
return getLeftSum(root);
}
private int getLeftSum(TreeNode node) {
int leftNodeSum = 0;
int rightNodeSum = 0;
if (node.right != null) {
rightNodeSum = getLeftSum(node.right);
}
if (node.left != null) {
leftNodeSum = getLeftSum(node.left);
// 要保证node.left是个叶子，才要它的值
if (node.left.left == null && node.left.right == null) {
return leftNodeSum + rightNodeSum + node.left.val;
}
}
return leftNodeSum + rightNodeSum;
}
}
以下代码引自《代码随想录》
思路：
思考一下，先判断null再进入，还是进入之后再判断null？其实这就是两份代码的不同之处。
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) {
return 0;
}
int leftValue = sumOfLeftLeaves(root.left); // 左
int rightValue = sumOfLeftLeaves(root.right); // 右
int midValue = 0;
if (root.left != null && root.left.left == null && root.left.right == null) {
midValue = root.left.val;
}
int sum = midValue + leftValue + rightValue; // 中
return sum;
}
}
思路：
迭代法。
如果是先判断null再入栈，可以ArrayDeque；如果有null值入栈，只能LinkedList
// 迭代法：判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) {
return 0;
}
// 如果是先判断null再入栈，可以ArrayDeque；如果有null值入栈，只能LinkedList
Deque<TreeNode> stack = new ArrayDeque<>();
stack.add(root);
int sum = 0;
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
// 当本节点的左节点不为空，左节点没有任何子节点，才算是左叶子。
if (node.left != null && node.left.left == null && node.left.right == null) {
sum += node.left.val;
}
if (node.right != null) {
stack.add(node.right);
}
if (node.left != null) {
stack.add(node.left);
}
}
return sum;
}
}