二叉搜索树转变为双向链表
输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
链接：
class Solution {
public:
bool isBalance = true;
bool IsBalanced_Solution(TreeNode* pRoot) {
// write code here
if (!pRoot)return true;
inOrderDepth(pRoot, isBalance);
return isBalance;
}
private:
int inOrderDepth(TreeNode* root, bool& isBalance) {
if (!root)return 0;
int leftDepth = inOrderDepth(root->left, isBalance);
int rightDepth = inOrderDepth(root->right, isBalance);
if (abs(leftDepth - rightDepth) > 1) isBalance = false;
return max(leftDepth, rightDepth) + 1;
}
};
递归问题思考
- 递归函数的返回值，这个在树的操作中，不同字数应该有不同的返回结果
- 递归函数的参数值，这个可以使应用传递的方式改变函数外的值，比如成员变量，参数可以不止一个
文档信息
- 本文作者：Chaojie Men
- 本文链接：https://menchaojie.github.io/2024/07/08/Judge_Balance_Binary_Tree/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）