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;}
}
