网络文学网站开发,电商详情页设计教程,项目管理流程,qux wordpress题目 给定一个二叉树#xff0c;判断它是否是高度平衡的二叉树。
本题中#xff0c;一棵高度平衡二叉树定义为#xff1a;一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 返回 true 。 示例 2: 给定二叉树 [1,2,…题目 给定一个二叉树判断它是否是高度平衡的二叉树。
本题中一棵高度平衡二叉树定义为一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 返回 true 。 示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4] 返回 false 。 思路
很多人一看题目觉得和求最大深度很像其实有很大区别。
这里强调一波概念 二叉树节点的深度指从根节点到该节点的最长简单路径边的条数。二叉树节点的高度指从该节点到叶子节点的最长简单路径边的条数。 但leetcode中强调的深度和高度很明显是按照节点来计算的如图 关于根节点的深度究竟是1 还是 0不同的地方有不一样的标准leetcode的题目中都是以节点为一度即根节点深度是1。但维基百科上定义用边为一度即根节点的深度是0我们暂时以leetcode为准。
因为求深度可以从上到下去查 所以需要前序遍历中左右而高度只能从下到上去查所以只能后序遍历左右中
有的同学一定疑惑为什么之前求最大深度中求的是二叉树的最大深度也用的是后序遍历。
那是因为代码的逻辑其实是求的根节点的高度而根节点的高度就是这棵树的最大深度所以才可以使用后序遍历。
在求二叉树最大深度中如果真正求取二叉树的最大深度代码应该写成如下前序遍历
class Solution {
public:int result;void getDepth(TreeNode* node, int depth) {result depth result ? depth : result; // 中if (node-left NULL node-right NULL) return ;if (node-left) { // 左depth; // 深度1getDepth(node-left, depth);depth--; // 回溯深度-1}if (node-right) { // 右depth; // 深度1getDepth(node-right, depth);depth--; // 回溯深度-1}return ;}int maxDepth(TreeNode* root) {result 0;if (root NULL) return result;getDepth(root, 1);return result;}
};可以看出使用了前序中左右的遍历顺序这才是真正求深度的逻辑
注意以上代码是为了把细节体现出来简化一下代码如下
class Solution {
public:int result;void getDepth(TreeNode* node, int depth) {result depth result ? depth : result; // 中if (node-left NULL node-right NULL) return ;if (node-left) { // 左getDepth(node-left, depth 1);}if (node-right) { // 右getDepth(node-right, depth 1);}return ;}int maxDepth(TreeNode* root) {result 0;if (root 0) return result;getDepth(root, 1);return result;}
};本题思路
递归
此时大家应该明白了既然要求比较高度必然是要后序遍历。
递归三步曲分析
1、明确递归函数的参数和返回值
参数当前传入节点。 返回值以当前传入节点为根节点的树的高度。
那么如何标记左右子树是否差值大于1呢
如果当前传入节点为根节点的二叉树已经不是二叉平衡树了还返回高度的话就没有意义了。
所以如果已经不是二叉平衡树了可以返回-1 来标记已经不符合平衡树的规则了。
// -1 表示已经不是平衡二叉树了否则返回值是以该节点为根节点树的高度
int getHeight(TreeNode* node)2、明确终止条件
递归的过程中依然是遇到空节点了为终止返回0表示当前节点为根节点的树高度为0
if (node NULL) {return 0;
}3、明确单层递归的逻辑
如何判断以当前传入节点为根节点的二叉树是否是平衡二叉树呢当然是其左子树高度和其右子树高度的差值。分别求出其左右子树的高度然后如果差值小于等于1则返回当前二叉树的高度否则返回-1表示已经不是二叉平衡树了。
int leftHeight getHeight(node-left); // 左
if (leftHeight -1) return -1;
int rightHeight getHeight(node-right); // 右
if (rightHeight -1) return -1;int result;
if (abs(leftHeight - rightHeight) 1) { // 中result -1;
} else {result 1 max(leftHeight, rightHeight); // 以当前节点为根节点的树的最大高度
}return result;代码精简之后如下
int leftHeight getHeight(node-left);
if (leftHeight -1) return -1;
int rightHeight getHeight(node-right);
if (rightHeight -1) return -1;
return abs(leftHeight - rightHeight) 1 ? -1 : 1 max(leftHeight, rightHeight);此时递归的函数就已经写出来了这个递归的函数传入节点指针返回以该节点为根节点的二叉树的高度如果不是二叉平衡树则返回-1。
最后本题整体递归代码如下
class Solution {
public:// 返回以该节点为根节点的二叉树的高度如果不是平衡二叉树了则返回-1int getHeight(TreeNode* node) {if (node NULL) {return 0;}int leftHeight getHeight(node-left);if (leftHeight -1) return -1;int rightHeight getHeight(node-right);if (rightHeight -1) return -1;return abs(leftHeight - rightHeight) 1 ? -1 : 1 max(leftHeight, rightHeight);}bool isBalanced(TreeNode* root) {return getHeight(root) -1 ? false : true;}
};迭代
在求二叉树的最大深度中我们可以使用层序遍历来求深度但是就不能直接用层序遍历来求高度了这就体现出求高度和求深度的不同。
本题的迭代方式可以先定义一个函数专门用来求高度。
这个函数通过栈模拟的后序遍历找每一个节点的高度其实是通过求传入节点为根节点的最大深度来求的高度
代码如下
// cur节点的最大深度就是cur的高度
int getDepth(TreeNode* cur) {stackTreeNode* st;if (cur ! NULL) st.push(cur);int depth 0; // 记录深度int result 0;while (!st.empty()) {TreeNode* node st.top();if (node ! NULL) {st.pop();st.push(node); // 中st.push(NULL);depth;if (node-right) st.push(node-right); // 右if (node-left) st.push(node-left); // 左} else {st.pop();node st.top();st.pop();depth--;}result result depth ? result : depth;}return result;
}然后再用栈来模拟后序遍历遍历每一个节点的时候再去判断左右孩子的高度是否符合代码如下
bool isBalanced(TreeNode* root) {stackTreeNode* st;if (root NULL) return true;st.push(root);while (!st.empty()) {TreeNode* node st.top(); // 中st.pop();if (abs(getDepth(node-left) - getDepth(node-right)) 1) { // 判断左右孩子高度是否符合return false;}if (node-right) st.push(node-right); // 右空节点不入栈if (node-left) st.push(node-left); // 左空节点不入栈}return true;
}整体代码如下
class Solution {
private:int getDepth(TreeNode* cur) {stackTreeNode* st;if (cur ! NULL) st.push(cur);int depth 0; // 记录深度int result 0;while (!st.empty()) {TreeNode* node st.top();if (node ! NULL) {st.pop();st.push(node); // 中st.push(NULL);depth;if (node-right) st.push(node-right); // 右if (node-left) st.push(node-left); // 左} else {st.pop();node st.top();st.pop();depth--;}result result depth ? result : depth;}return result;}public:bool isBalanced(TreeNode* root) {stackTreeNode* st;if (root NULL) return true;st.push(root);while (!st.empty()) {TreeNode* node st.top(); // 中st.pop();if (abs(getDepth(node-left) - getDepth(node-right)) 1) {return false;}if (node-right) st.push(node-right); // 右空节点不入栈if (node-left) st.push(node-left); // 左空节点不入栈}return true;}
};当然此题用迭代法其实效率很低因为没有很好的模拟回溯的过程所以迭代法有很多重复的计算。
虽然理论上所有的递归都可以用迭代来实现但是有的场景难度可能比较大。
例如都知道回溯法其实就是递归但是很少人用迭代的方式去实现回溯算法
因为对于回溯算法已经是非常复杂的递归了如果再用迭代的话就是自己给自己找麻烦效率也并不一定高。
