判断二叉树是否为平衡二叉树
一、题目
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
leetcode：https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/
二、思路
判断一颗二叉树是否为平衡树，那就判断这颗二叉树的左子树是否为平衡树、右子树是否为平衡树。并且在判断子树的时候记录子树的高度即可。
用一个变量来记录是否为平衡二叉树，如果在判断的中间过程，发现不是平衡的了，马上置为 false，保证这个 bool 变量是个指针或引用。左右子树都是平衡的，那就返回左右子树的高度，看当前节点所代表的树是否平衡。
三、code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <iostream>
#include <algorithm>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
explicit TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};
class Solution {
public:
bool isBalanced(TreeNode* root) {
bool res = true;
get_hight(root, 1, res);
return res;
}
private:
int get_hight(TreeNode* node, int level, bool& res) {
if (node == nullptr) {
return level;
}
int left_high = get_hight(node->left, level+1, res);
if (!res) {
return level;
}
int right_high = get_hight(node->right, level+1, res);
if (!res) {
return level;
}
if (std::abs(left_high - right_high) > 1) {
res = false;
}
return std::max(left_high, right_high);
}
};
|
每个节点只遍历了一次，因此时间复杂度为 O(n)