代码随想录算法训练营Day15 | 222.完全二叉树的节点个数、110.平衡二叉树、257. 二叉树的所有路径、404.左叶子之和
目录
222.完全二叉树的节点个数
题目
222. 完全二叉树的节点个数 - 力扣（LeetCode）
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例1：
输入：root = [1,2,3,4,5,6]
输出：6
示例2：
输入：root = []
输出：0
示例3：
输入：root = [1]
输出：1
思路
按照普通二叉树解题，直接遍历整个二叉树，时间复杂度为 O(n)，可以使用层序遍历或者递归法后序遍历。
再按照完全二叉树的特性解题：完全二叉树只有两种情况，一种是满二叉树，一种是最后一层叶子节点没有满。
对于情况一，总节点数等于 2depth-1 ，根节点深度为1。
对于情况二，分别递归左孩子和右孩子，递归到某一深度时一定会有孩子为满二叉树，然后按照情况一进行计算。
在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，就说明是是满二叉树。
题解
普通二叉树解法：
class Solution {
public int countNodes(TreeNode root) {
return count(root);
}
int count(TreeNode root) {
if (root == null)
return 0;
int left = count(root.left);
int right = count(root.right);
return left + right + 1;
}
}
完全二叉树解法：
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;
}
}
110.平衡二叉树
题目
给定一个二叉树，判断它是否是 平衡二叉树
示例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
思路
- 确定递归函数的返回值是 以当前节点为根节点的树的高度，如果以当前节点为根节点的二叉树不是平衡二叉树，代表整个树都不是平衡二叉树，直接返回-1进行标记即可。
- 确定终止条件，遇到空节点时返回0，表示以当前节点为根节点的树高度为0。
- 递归逻辑，分别求当前节点左子树和右子树的高度，再进行验证，若差值大于1则不是平衡二叉树，返回-1，如果是平衡二叉树就返回当前二叉树的高度，即
max(leftHeight, rightHeight) + 1。
题解
递归法：
class Solution {
public boolean isBalanced(TreeNode root) {
return getHeight(root) != -1;
}
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;
if (Math.abs(leftHeight - rightHeight) > 1)
return -1;
return Math.max(leftHeight, rightHeight) + 1;
}
}
257. 二叉树的所有路径
题目
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例1：
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]
示例2：
输入：root = [1]
输出：["1"]
提示：
- 树中节点的数目在范围
[1, 100]内 -100 <= Node.val <= 100
思路
首先确定遍历顺序为前序遍历，方便让父节点指向子节点。
该题涉及回溯算法，因为要把路径记录下来，需要回溯来回退一个路径来进入另一条路径：
定义一个实时更新的列表 path 存放路径，一个列表 res 存放结果。
回溯和递归一一对应，每有一个递归，就要有一个回溯。
题解
递归法：
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
getPath(root, path, res);
return res;
}
void getPath(TreeNode root, List path, List res) {
//前序遍历，先放入中间节点
path.add(root.val);
//遇到叶子节点
if (root.left == null && root.right == null) {
StringBuilder str = new StringBuilder();
for (int i = 0; i < path.size() - 1; i++) {
str.append(path.get(i)).append("->");
}
str.append(path.get(path.size() - 1));
res.add(str.toString());
return;
}
//递归和回溯同时进行，放在一个代码块中
if (root.left != null) {
getPath(root.left, path, res);
path.remove(path.size() - 1);
}
if (root.right != null) {
getPath(root.right, path, res);
path.remove(path.size() - 1);
}
}
}
404.左叶子之和
题目
给定二叉树的根节点 root ，返回所有左叶子之和。
示例1：
输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
示例2：
输入: root = [1]
输出: 0
提示:
- 节点数在
[1, 1000]范围内 -1000 <= Node.val <= 1000
思路
判断一个节点是否是左叶子节点，必须通过其父节点进行判断。
通过递归求取左子树左叶子之和，再求取右子树左叶子之和，相加即可。
此外，本题还可以使用层序遍历解题（偷懒了
题解
递归法：
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);
if (root.left != null && root.left.left == null && root.left.right == null)
leftValue = root.left.val;
return leftValue + rightValue;
}
}
原文地址：https://blog.csdn.net/jiabao0520/article/details/142525523
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！