代码随想录刷题day15丨110.平衡二叉树，257. 二叉树的所有路径， 404.左叶子之和，222.完全二叉树的节点个数

1.题目

1.1平衡二叉树（优先掌握递归）

题目链接：110. 平衡二叉树 - 力扣（LeetCode）
视频讲解：后序遍历求高度，高度判断是否平衡 | LeetCode：110.平衡二叉树_哔哩哔哩_bilibili
文档讲解：https://programmercarl.com/0110.%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91.html
解题思路：递归（后序遍历）

代码：

/*** 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) {int res = getHeight(root);return res == -1 ? false:true;}// 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了则返回-1public int getHeight(TreeNode node){if(node == null){return 0;}int leftHeight = getHeight(node.left);if(leftHeight == -1){return -1;}int rightHeight = getHeight(node.right);if(rightHeight == -1){return -1;}if(Math.abs(leftHeight - rightHeight) > 1){return -1;}else{int result = 1 + Math.max(leftHeight,rightHeight);return result;}}
}

总结：
- 求高度用后序遍历，求深度用前序遍历

1.2二叉树的所有路径（优先掌握递归）

题目链接：257. 二叉树的所有路径 - 力扣（LeetCode）
视频讲解：递归中带着回溯，你感受到了没？| LeetCode：257. 二叉树的所有路径_哔哩哔哩_bilibili
文档讲解：https://programmercarl.com/0257.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%89%80%E6%9C%89%E8%B7%AF%E5%BE%84.html
解题思路：递归（前序遍历）
- 这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。
- 这道题目涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。

代码：

/*** 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 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;}public void traversal(TreeNode node, List<Integer> paths, List<String> res){paths.add(node.val);//遇到叶子结点if(node.left == null && node.right == null){// StringBuilder用来拼接字符串，速度更快StringBuilder s = new StringBuilder();for(int i = 0;i < paths.size() - 1;i++){s.append(paths.get(i)).append("->");}s.append(paths.get(paths.size() -1));//记录最后一个节点String s1 = s.toString();res.add(s1);// 收集一个路径return;}if(node.left != null){traversal(node.left,paths,res);paths.remove(paths.size() -1);// 回溯}if(node.right != null){traversal(node.right,paths,res);paths.remove(paths.size() -1);// 回溯}}
}

总结：
- 回溯和递归是一一对应的，有一个递归，就要有一个回溯

1.3左叶子之和（优先掌握递归）

题目链接：404. 左叶子之和 - 力扣（LeetCode）
视频讲解：二叉树的题目中，总有一些规则让你找不到北 | LeetCode：404.左叶子之和_哔哩哔哩_bilibili
文档讲解：https://programmercarl.com/0404.%E5%B7%A6%E5%8F%B6%E5%AD%90%E4%B9%8B%E5%92%8C.html
解题思路：递归（后序遍历）
- 要注意是判断左叶子，不是二叉树左侧节点，所以不要上来想着层序遍历。
- 左叶子的明确定义：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点

在这里插入图片描述

判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。
如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子

代码：

/*** 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 int sumOfLeftLeaves(TreeNode root) {return traversal(root);}public int traversal(TreeNode node){if(node == null){return 0;}if(node.left == null && node.right == null){return 0;}int leftNum = traversal(node.left);//左if(node.left != null && node.left.left == null && node.left.right == null){leftNum = node.left.val;}int rightNum = traversal(node.right);//右int sum = leftNum + rightNum;//中return sum;}
}

总结：
- 递归的遍历顺序为后序遍历（左右中），是因为要通过递归函数的返回值来累加求取左叶子数值之和。

1.4完全二叉树的节点个数（优先掌握递归）

题目链接：222. 完全二叉树的节点个数 - 力扣（LeetCode）
视频讲解：要理解普通二叉树和完全二叉树的区别！ | LeetCode：222.完全二叉树节点的数量_哔哩哔哩_bilibili
文档讲解：https://programmercarl.com/0222.%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0.html
解题思路：递归（后序遍历）
- 完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
  - 对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
  - 对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
  - 可以看出如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量。
- 这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢？
  - 在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。

代码：

/*** 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 {/*** 针对完全二叉树的解法** 满二叉树的结点数为：2^depth - 1*/public int countNodes(TreeNode root) {return getNum(root);}public int getNum(TreeNode node){if(node == null){return 0;}TreeNode leftNode = node.left;TreeNode rightNode = node.right;int leftLength = 0;// 这里初始为0是有目的的，为了下面求指数方便int rightLength = 0;while(leftNode != null){leftNode = leftNode.left;leftLength++;}while(rightNode != null){rightNode = rightNode.right;rightLength++;}if(leftLength == rightLength){return (2 << leftLength) - 1;// 注意(2<<1) 相当于2^2，所以leftDepth初始为0}int leftNum = getNum(node.left);//左int rightNum = getNum(node.right);//右int res = leftNum + rightNum + 1;//中return res;}
}

class Solution {// 通用递归解法public int countNodes(TreeNode root) {if(root == null) {return 0;}return countNodes(root.left) + countNodes(root.right) + 1;}
}