死磕算法系列文章
“Leetcode : https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/
“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_42_isBalanced/Solution.java
“题目描述 :输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。 难度:简单
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
例如:给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
此题为 剑指offer | 面试题41:二叉树的深度 的拓展
思路:平衡二叉树的条件:左子树是平衡二叉树,右子树是平衡二叉树,左右子树高度不超过 1。
isBalanced(root)
函数: 判断树 root
是否平衡
root
为空,则直接返回 true ;返回值: 所有子树都需要满足平衡树性质,因此以下三者使用与逻辑 && 连接;
Math.abs(depth(root.left) - depth(root.right)) <= 1
:判断 当前子树 是否是平衡树;isBalanced(root.left)
:先序遍历递归,判断 当前子树的左子树 是否是平衡树;isBalanced(root.right)
:先序遍历递归,判断 当前子树的右子树 是否是平衡树;depth(TreeNode root)
函数: 计算树 root
的深度
root
为空,即越过叶子节点,则返回高度 0 ;isBalanced(root)
遍历树所有节点,判断每个节点的深度 depth(root)
需要遍历 各子树的所有节点 。Java
package com.nateshao.sword_offer.topic_42_isBalanced;
/**
* @date Created by 邵桐杰 on 2022/1/23 19:26
* @微信公众号 千羽的编程时光
* @个人网站 www.nateshao.cn
* @博客 https://nateshao.gitee.io
* @GitHub https://github.com/nateshao
* @Gitee https://gitee.com/nateshao
* Description:
*/
public class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
private int depth(TreeNode root) {
if (root == null) return 0;
return Math.max(depth(root.left), depth(root.right)) + 1;
}
// public boolean isBalanced(TreeNode root){
// if(root == null) {
// return true;
// }
// boolean condition = Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1;
// return condition && isBalanced(root.left) && isBalanced(root.right);
// }
// public int maxDepth(TreeNode root) {
// if (root == null) {
// return 0;
// }
// int left = maxDepth(root.left);
// int right = maxDepth(root.right);
// return Math.max(left, right) + 1;
// }
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
}
Go
func isBalanced(node *TreeNode) bool {
return node == nil || isBalanced(node.Left) &&
math.Abs(height(node.Left)-height(node.Right)) <= 1 && // 左右子树高度不超过 1
isBalanced(node.Right)
}
//计算节点最大深度
func height(node *TreeNode) float64 {
if node == nil {
return 0
}
return math.Max(height(node.Left), height(node.Right)) + 1
}
“思路是对二叉树做后序遍历,从底至顶返回子树深度,若判定某子树不是平衡树则 “剪枝” ,直接向上返回。
recur(root)
函数:
当节点root
左 / 右子树的深度差 ≤1 :则返回当前子树的深度,即节点 root
的左 / 右子树的深度最大值 +1 ( max(left, right) + 1
);
root
左 / 右子树的深度差 >2 :则返回 −1 ,代表 此子树不是平衡树 。终止条件:
root
为空:说明越过叶节点,因此返回高度 0 ;当左(右)子树深度为 -1−1 :代表此树的 左(右)子树 不是平衡树,因此剪枝,直接返回 −1 ;isBalanced(root)
函数:
recur(root) != -1
,则说明此树平衡,返回 true ;否则返回 false 。复杂度分析:
class Solution {
public boolean isBalanced(TreeNode root) {
return recur(root) != -1;
}
private int recur(TreeNode root) {
if (root == null) return 0;
int left = recur(root.left);
if(left == -1) return -1;
int right = recur(root.right);
if(right == -1) return -1;
return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
}
}
参考链接:https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/solution/mian-shi-ti-55-ii-ping-heng-er-cha-shu-cong-di-zhi/