代码随想录算法训练营day17 | 题目110、题目257、题目404、题目543、题目572
题目一描述
110. 平衡二叉树
给定一个二叉树，判断它是否是 平衡二叉树
平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1。
示例 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] 内
-10^4 <= Node.val <= 10^4
解题思路
注意高度是从底到顶计算，深度是从顶到底计算。
平衡二叉树代表，每个结点的左右子树的最大深度相差不超过1，同时左右子树都是平衡二叉树。
容易想到的是遍历每个结点，判断其左右子树是否为平衡二叉树，同时求左右子树最大深度。但是对每个结点都要求一遍左右子树的深度，复杂度很高。
优化的方法是，在求高度的时候就比较左右子树深度，如果相差大于1就返回负值（深度均大于0），同时如果本节点左右子树深度中有一个是-1，就停止遍历并返回-1。这样最多求所有的结点深度一遍即可。
代码实现
方法一：
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null)
return true;
if (Math.abs(getDepth(root.left) - getDepth(root.right)) > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
public int getDepth(TreeNode root) {
if (root == null)
return 0;
return Math.max(getDepth(root.left), getDepth(root.right)) + 1;
}
}
方法二：
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null)
return true;
return getDepth(root) == -1 ? false : true;
}
public int getDepth(TreeNode root) {
if (root == null)
return 0;
int leftDepth = getDepth(root.left);
if(leftDepth == -1){
return -1;
}
int rightDepth = getDepth(root.right);
if(rightDepth == -1){
return -1;
}
if (Math.abs(leftDepth - rightDepth) > 1) {
return -1;
}
return Math.max(leftDepth, rightDepth) + 1;
}
}
题目二描述
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]
示例 2：
输入：root = [1]
输出：["1"]
提示：
树中节点的数目在范围 [1, 100] 内
-100 <= Node.val <= 100
解题思路
使用回溯，注意回溯的是path
深度优先遍历，每次进入下一个结点之前，复制当前路径并添加连接符，遇到叶子结点就加入结果集。
注意字符串是不可变的，所以每次对字符串参数作修改，其实是相当于复制了一遍这个字符串，类似于值传递。
广度优先遍历也可以，需要一个同步的辅助队列来存储追踪path。也可以只用一个队列，每次出队列两次，入队列也做同步操作。那样的话队列定义为 Queue<Object>，取出时类型转换。
记住该用辅助空间就用辅助空间。
代码实现
方法一：
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
dfs(root, "", res);
return res;
}
private void dfs(TreeNode root, String path, List<String> res) {
path = path + root.val;
if (root.left == null && root.right == null) {
res.add(path);
}
if (root.left != null) {
dfs(root.left, path + "->", res);
}
if (root.right != null) {
dfs(root.right, path + "->", res);
}
}
}
方法二：
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();// 存最终的结果
Queue<TreeNode> queue = new ArrayDeque<>();
Queue<String> path = new ArrayDeque<>();
queue.offer(root);
path.offer(String.valueOf(root.val));
while (!queue.isEmpty()) {
TreeNode temp = queue.poll();
String temp_path = path.poll();
if (temp.left == null && temp.right == null) {
res.add(temp_path);
}
if (temp.left != null) {
queue.offer(temp.left);
path.offer(new StringBuffer(temp_path).append("->").append(temp.left.val).toString());
}
if (temp.right != null) {
queue.offer(temp.right);
path.offer(new StringBuffer(temp_path).append("->").append(temp.right.val).toString());
}
}
return res;
}
}
题目三描述
给定二叉树的根节点 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) {
int res = 0;
boolean flag = false;
return dfs(root, res, flag);
}
private int dfs(TreeNode root, int res, boolean flag) {
if(root == null){
return 0;
}
if (root.left == null && root.right == null) {
return flag ? res + root.val : 0;
}
return dfs(root.left, res, true) + dfs(root.right, res, false);
}
}
方法二：
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
int res = 0;
boolean flag = false;
Queue<Object> queue = new ArrayDeque<>();
queue.offer(flag);
queue.offer(root);
while (!queue.isEmpty()) {
flag = (boolean) queue.poll();
TreeNode temp = (TreeNode) queue.poll();
if (temp.left == null && temp.right == null && flag) {
res += temp.val;
}
if (temp.left != null) {
queue.offer(true);
queue.offer(temp.left);
}
if (temp.right != null) {
queue.offer(false);
queue.offer(temp.right);
}
}
return res;
}
}
题目四描述
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1：
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：
输入：root = [1,2]
输出：1
提示：
树中节点数目在范围 [1, 10^4] 内
-100 <= Node.val <= 100
解题思路
通过该节点的最大路径长度 = 左子树最大高度 + 右子树最大高度
所以需要遍历一遍所有节点，在求得本节点最大高度的时候，也可以同步更新result。
因为递归是把结果值自底向上，所以本质上是高度累加的过程。
这个dfs的过程只需要一次，因为dfs的过程中每个结点的需要的信息都可以得到，所以不用dfs套dfs，直接在求高度的时候可以更新结果值。与求是否包含子树的那道题不一样。
代码实现
方法一：
class Solution {
int res = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxHeight(root);
return res;
}
public int maxHeight(TreeNode root) {
if (root == null) {
return 0;
}
int left_height = maxHeight(root.left);
int right_height = maxHeight(root.right);
res = Math.max(res, left_height + right_height); // 通过该节点的最大路径长度 = 左子树最大高度 + 右子树最大高度
return Math.max(left_height, right_height) + 1;
}
}
技巧总结
题目四描述
572. 另一棵树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例 1：
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
示例 2：
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false
提示：
root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-10^4 <= root.val <= 10^4
-10^4 <= subRoot.val <= 10^4
解题思路
针对每个结点做子树是否相等的判断，dfs套dfs。
这个check的dfs过程无法一次就得到所有需要的结果信息，所以必须dfs套dfs。
代码实现
方法一：
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null)
return false;
if (check(root, subRoot)) {
return true;
}
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
private boolean check(TreeNode root, TreeNode subRoot) {
if (root == null && subRoot == null) {
return true;
}
if (root == null || subRoot == null || root.val != subRoot.val)
return false;
return check(root.left, subRoot.left) && check(root.right, subRoot.right);
}
}
