剑指offer——平衡二叉树---AI那点小事

概要

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

思路

如果树为空，返回true。否则递归判断每个树节点的其左右子树高度之差的绝对值是否为0或者1，若是返回true，不是返回false。 注明：这里平衡二叉树不需要是二叉排序树，国内教材为了讲述方便，默认平衡二叉树前提为二叉排序树。

C++ AC代码#include <iostream> #include <cmath> using namespace std; /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: bool IsBalanced_Solution(TreeNode* pRoot) { if(pRoot == NULL){ return true; } return this->check_Height(pRoot); } bool check_Height(TreeNode* pRoot){ if(pRoot == NULL){ return true; } int left = this->TreeDepth(pRoot->left); int right = this->TreeDepth(pRoot->right); bool flag; if(abs(left-right) <= 1){ return this->IsBalanced_Solution(pRoot->left) && this->IsBalanced_Solution(pRoot->right); }else{ return false; } } int TreeDepth(TreeNode* pRoot){ if(pRoot == NULL){ return 0; } int left = this->TreeDepth(pRoot->left); int right = this->TreeDepth(pRoot->right); return (left>right)?left+1:right+1; } };

---来自腾讯云社区的---AI那点小事