15.代码随想录算法训练营第十五天|（递归）110. 平衡二叉树，257. 二叉树的所有路径*，404. 左叶子之和，222.完全二叉树的节点个数
给定一个二叉树，判断它是否是 平衡二叉树
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：
输入：root = []
输出：true
提示：
- 树中的节点数在范围
[0, 5000]内 -104 <= Node.val <= 104
思想：求高度的话用后序遍历，求深度的话用前序遍历。
- 参数是node，返回值是int，左右子树的高度。
- if（node==null）return 0；
- 单层逻辑：如果不是平衡二叉树就返回-1.
- lefthight ==-1
- righthight==-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 {
public boolean isBalanced(TreeNode root) {
return getHight(root)!=-1;
}
public int getHight(TreeNode node){
if(node == null) return 0;
int leftHight = getHight(node.left);
if(leftHight == -1) return -1;
int rightHight = getHight(node.right);
if(rightHight == -1) return -1;
if(Math.abs(leftHight-rightHight)<=1){
return Math.max(leftHight,rightHight)+1;
}else{
return -1;
}
}
}
257. 二叉树的所有路径 - 力扣（LeetCode）
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]
示例 2：
输入：root = [1]
输出：["1"]
提示：
- 树中节点的数目在范围
[1, 100]内 -100 <= Node.val <= 100
思想：
需要显式回溯：当算法需要记录路径或复杂状态，并在完成某个分支后返回到先前状态时。
不需要显式回溯：当算法只需计算结果，且递归调用本身能自然恢复状态时。
/**
* 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){
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));
res.add(sb.toString());
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);
}
}
}
404. 左叶子之和 - 力扣（LeetCode）
给定二叉树的根节点 root ，返回所有左叶子之和。
示例 1：
输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
示例 2:
输入: root = [1]
输出: 0
提示:
- 节点数在
[1, 1000]范围内 -1000 <= Node.val <= 1000
/**
* 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);
int rightValue = sumOfLeftLeaves(root.right);
int midSum = 0;
if(root.left != null && root.left.left == null && root.left.right == null){
midSum = root.left.val;
}
int sum = midSum + leftValue + rightValue;
return sum;
}
}
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2h 个节点。
222. 完全二叉树的节点个数 - 力扣（LeetCode）
示例 1：
输入：root = [1,2,3,4,5,6]
输出：6
示例 2：
输入：root = []
输出：0
示例 3：
输入：root = [1]
输出：1
提示：
- 树中节点的数目范围是
[0, 5 * 104] 0 <= Node.val <= 5 * 104- 题目数据保证输入的树是 完全二叉树
**进阶：**遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？
解法一：不考虑是否是完全二叉树，用后序遍历，因为要统计自己孩子节点的数量。
/**
* 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 countNodes(TreeNode root) {
if(root == null) return 0;
return countNodes(root.left) + countNodes(root.right) +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 int countNodes(TreeNode root) {
//终止条件包括判断是不是满二叉树在内
if (root == null) return 0;
TreeNode left = root.left;
TreeNode right = root.right;
int leftDepth = 0, rightDepth = 0;
while (left != null) {
left = left.left;
leftDepth++;
}
while (right != null) {
right = right.right;
rightDepth++;
}
if (leftDepth == rightDepth) {
return (2 << leftDepth) - 1;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
