110.平衡二叉树 （优先掌握递归）
题目链接/文章讲解/视频讲解
再一次涉及到，什么是高度，什么是深度，可以巩固一下。
思路
- 任何节点的左右子树高度差小于等于1则是平衡二叉树
- 高度和深度：高度：到叶子节点的距离；深度：到根节点的距离。这道题求高度，就是后序遍历。
伪代码
//定义递归函数，参数和返回值
private int getHeight(TreeNode root){
//终止条件 空节点高度为0
if(node == null) return 0;
//发现任何一个节点不符合平衡二叉树的定义，直接返回-1
//采用后序遍历 左右中
int leftHeight = getHeight(root.left); //左子树高度
if(leftHeight == -1) return -1; //左子树高度==-1不符合平衡二叉树
int rightHeight = getHeight(root.right); //右子树高度
if(rightHeight == -1) return -1;
int result;
// 一定要把中写在左右子树的后面，才能获取左右的情况返回给父节点
if(Math.abs(leftHeight - rightHeight) > 1){ //相减绝对值大于1
result = -1;
}else{
// 左右子树高度取最大值再加一
result = Math.max(leftHeight, rightHeight) + 1;
}
return result;
}
/**
* 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; //为什么这里要这么写
}
private int getHeight(TreeNode root){
if(root == null) return 0;
int leftHeight = getHeight(root.left);
if(leftHeight == -1) return -1;
int rightHeight = getHeight(root.right);
if(rightHeight == -1) return -1;
return Math.abs(leftHeight - rightHeight) > 1 ? -1 : (Math.max(leftHeight, rightHeight) + 1);
}
}
257. 二叉树的所有路径 （优先掌握递归）
思路
- 返回从根节点到叶子节点的所有路径
- 使用前序遍历：这样才能让父节点指向孩子节点，才能把路径输出出来
- 只要有递归就一定有回溯
- 为什么会有回收的过程：一个容器来收集路径，怎么把一条路径收集完后，把子节点弹出去，重新回到根节点记录新路径呢？所以有回溯。
伪代码
//1. 定义函数，定义参数和返回值
// root 根节点； paths 记录单条路径的数组；res 记录最后结果，也是返回值
private void traversal(TreeNode node, List<Integer> paths, List<String> res) {
//3. 前序遍历，中节点，因为遍历到叶子节点就结束了，所以要把叶子节点放进入才中止
paths.add(node.val);
//2. 确定终止条件：遍历到叶子节点
if(node.left == null && node.right == null){
// 要把paths转化成String然后元素之间加上"->"，代码略
StringBuilder sb = new StringBuilder();// StringBuilder用来拼接字符串
……
res.add(sb.toString())
return;
}
//向左递归
if(node != null){
traversal(root.left, paths, res);
paths.remove(paths.size() - 1);// 回溯，可以隐藏在参数中
}
//向右递归
if（node != null）{
traversal(root.right, paths, res);
paths.remove(paths.size() - 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 {
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 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));
res.add(s.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);
}
}
}
404.左叶子之和 （优先掌握递归）
题目链接/文章讲解/视频讲解
其实本题有点文字游戏，搞清楚什么是左叶子，剩下的就是二叉树的基本操作。
思路
- 左叶子节点的定义：一定是叶子节点（子节点为空）；一定是父节点的左孩子。
- 和之前二叉树题目的区别：无法判断叶子节点是不是父节点的左孩子，所以判断条件是：一个节点的左孩子不为空，同时左孩子的左右孩子都为空。
- 使用后序遍历，因为要一层一层向上返回
伪代码
public int sumOfLeftLeaves(TreeNode root) {
//终止条件
if(root == null) return 0;
if(root.left == null && root.right == null) return 0; // 不写也行，只是递归多了一层
//单层递归的逻辑
int leftNum = sumOfLeftLeaves(root.left);
//左孩子不为空，同时左孩子为叶子节点
if(root.left != null && root.left.left != null && root.right.right != null){
leftNum = root.left.val;
}
int rightNum = sumOfLeftLeaves(root.right);
int sum = leftNum + rightNum
return sum;
}
/**
* 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) {
if (root == null) return 0;
if (root.left == null && root.right == null) return 0;
int leftValue = sumOfLeftLeaves(root.left); // 左
if (root.left != null && root.left.left == null && root.left.right == null) { // 左子树就是一个左叶子的情况
leftValue = root.left.val;
}
int rightValue = sumOfLeftLeaves(root.right); // 右
int sum = leftValue + rightValue; // 中
return sum;
}
}
222.完全二叉树的节点个数（优先掌握递归）
题目链接/文章讲解/视频讲解
需要了解，普通二叉树 怎么求，完全二叉树又怎么求
思路
- 如果是普通的二叉树，就是遍历节点
后序遍历
class Solution {
// 通用递归解法
public int countNodes(TreeNode root) {
if(root == null) {
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
- 利用完全二叉树的特性的写法
- 完全二叉树的定义：除了底层节点每一层都是满的，底层节点都集中在该层最左边
- 只要知道深度，节点数量就是2的深度次方 -1
- 所以就是左子树的数量+右子树的数量+1
- 如果是满二叉树，往左右两边遍历的深度相等；如果子树不相等则不是满二叉树，那么就继续向下递归，一定可以遇到符合满足条件的节点
public int countNodes(TreeNode root) {
//终止条件
if (root == null) return 0;
//遇到子树为满二叉树，也要返回结果并终止
TreeNode left = root.left;
TreeNode right = root.right;
int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便
while (left != null) { // 求左子树深度
left = left.left;
leftDepth++;
}
while (right != null) { // 求右子树深度
right = right.right;
rightDepth++;
}
if (leftDepth == rightDepth) {
return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
