扫码关注微信公众号
回复“面试手册”，获取本站PDF版
回复“简历”，获取高质量简历模板
回复“加群”，加入程序员交流群
回复“电子书”，获取程序员类电子书
题目描述
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [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 。
限制：
- 0 <= 树的结点个数 <= 10000
题解1
(DFS,递归) O(n)
这道题目其实就是在求二叉树中的每个节点最大深度（高度）的过程中判断以当前节点为根的树是否为二叉平衡树。
定义一个全局答案，首先假设是平衡二叉树，递归后序遍历二叉树，遍历的过程中如果遇到不是平衡二叉树的节点，说明整棵二叉树就不是平衡二叉树。
时间复杂度
二叉树的每个节点只会被遍历一次，所以时间复杂度为 O(n)。
空间复杂度
O(logn)，最坏情况下 O(n)。
C++ 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool ans = true;
int dfs(TreeNode* root) {
if (!root) return 0;
int lh = dfs(root->left), rh = dfs(root->right);
if (abs(lh - rh) > 1) ans = false;
return max(lh, rh) + 1;
}
bool isBalanced(TreeNode* root) {
dfs(root);
return ans;
}
};Java 代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
boolean ans = true;
public boolean isBalanced(TreeNode root) {
dfs(root);
return ans;
}
private int dfs(TreeNode root) {
if (root == null) return 0;
int lh = dfs(root.left), rh = dfs(root.right);
if (Math.abs(lh - rh) > 1) ans = false;
return Math.max(lh, rh) + 1;
}
}Python 代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
self.ans = True
def dfs(root):
if not root:
return 0
lh = dfs(root.left)
rh = dfs(root.right)
if abs(lh - rh) > 1:
self.ans = False
return max(lh, rh) + 1
dfs(root)
return self.ans题解 2
(BFS,迭代) O(n^2)
首先使用层序遍历 BFS 写一个求节点高度的函数。
迭代法前序遍历二叉树，对于每个节点判断它的左子树和右子树的高度之差绝对值是否大于 1，如果大于 1 说明不是平衡二叉树，否则当所有节点遍历完成后，说明该树是一棵平衡二叉树。
时间复杂度
求二叉树的高度所需的时间为 O(n)，每个节点都需要求一次高度，所以时间复杂度为 O(n^2)。
空间复杂度
最坏情况下每次求二叉树的高度所需系统栈空间为 O(n)。
C++ 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int getDepth(TreeNode* root) {
queue<TreeNode*> q;
if (root) q.push(root);
int depth = 0;
while (q.size()) {
depth ++ ;
int sz = q.size();
while (sz -- ) {
auto t = q.front();
q.pop();
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
}
return depth;
}
bool isBalanced(TreeNode* root) {
stack<TreeNode*> stk;
if (root) stk.push(root);
while (stk.size()) {
auto t = stk.top();
stk.pop();
if (abs(getDepth(t->left) - getDepth(t->right)) > 1) return false;
if (t->right) stk.push(t->right);
if (t->left) stk.push(t->left);
}
return true;
}
};Java 代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
return isBalancedWithDepth(root) != -1;
}
private int isBalancedWithDepth(TreeNode root) {
if (root == null) return 0;
int leftDepth = isBalancedWithDepth(root.left);
if (leftDepth == -1) return -1;
int rightDepth = isBalancedWithDepth(root.right);
if (rightDepth == -1) return -1;
if (Math.abs(leftDepth - rightDepth) > 1) return -1;
return Math.max(leftDepth, rightDepth) + 1;
}
}Python 代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
return self.isBalancedWithDepth(root) != -1
def isBalancedWithDepth(self, root: TreeNode) -> int:
if not root:
return 0
leftDepth = self.isBalancedWithDepth(root.left)
if leftDepth == -1:
return -1
rightDepth = self.isBalancedWithDepth(root.right)
if rightDepth == -1:
return -1
if abs(leftDepth - rightDepth) > 1:
return -1
return max(leftDepth, rightDepth) + 1本文由读者提供，Github地址：https://github.com/tonngw
点击面试手册，获取本站面试手册PDF完整版