c++_cmake入门最佳实践

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

思路

• 利用二叉树长度求法，递归求解（后序遍历）
• 递归判断是否满足平衡二叉树的条件，左右子树的深度相差 <= 1
• 后序遍历的应用

// 输入一棵二叉树，判断该二叉树是否是平衡二叉树。

// 利用求树的深度算法实现
class Solution {
public:
    //  递归求pRoot的深度
    int TreeDepth(TreeNode* pRoot)
    {
        if (pRoot == nullptr) {
            return 0;
        }
        
        int left = TreeDepth(pRoot->left) + 1;
        int right = TreeDepth(pRoot->right) + 1;
        
        return right > left ? right:left;
    }
    // 递归判断是否为平衡二叉树
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if (pRoot == nullptr) {
            return true;
        }
        
        int left = TreeDepth(pRoot->left) + 1;
        int right = TreeDepth(pRoot->right) + 1;
        // 平衡判断
        int diff = left - right;
        if (diff > 1 || diff < -1) {
            return false;
        }
        
        return IsBalanced_Solution(pRoot->left) &&
            IsBalanced_Solution(pRoot->right);
    }
};

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com