《程序员面试金典》二叉树平衡检查

题目链接：?rp=1&ru=/ta/cracking-the-coding-interview&qru=/ta/cracking-the-coding-interview/question-ranking

题目描述实现一个函数，检查二叉树是否平衡，平衡的定义如下，对于树中的任意一个结点，其两颗子树的高度差不超过1。给定指向树根结点的指针TreeNode* root，，请返回一个bool，代表这棵树是否平衡。思路最简单的方法是每个节点都使用递归求解其深度，然后再去比较，但是这样无疑会带来大量无谓的操作，效率不高我们可以从根节点一直搜索到叶子结点，并在回溯的过程中返回其深度，并同层相比较，一旦有不满足的情况，就直接结束。

/*struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}};*/class Balance{public:bool isBalance(TreeNode *root){// write code hereif(root==nullptr)return true;return checkHeight(root)>=0;}int checkHeight(TreeNode *root){if(root==nullptr)return 0;int leftHeight = checkHeight(root->left);if(leftHeight==-1)return -1;int rightHeight = checkHeight(root->right);if(rightHeight==-1)return -1;if(abs(leftHeight-rightHeight)>1)return -1;return max(leftHeight,rightHeight)+1;}};

你不能左右天气，但你能转变你的心情

相关文章：

你感兴趣的文章：

标签云：