93-平衡二叉樹

給定一個二叉樹,確定它是高度平衡的。對于這個問題,一棵高度平衡的二叉樹的定義是：一棵二叉樹中每個節點的兩個子樹的深度相差不會超過1。

您在真實的面試中是否遇到過這個題？ Yes
樣例
給出二叉樹 A={3,9,20,#,#,15,7}, B={3,#,20,15,7}

二叉樹A是高度平衡的二叉樹，但是B不是

標簽
分治法 遞歸

思路

采用遞歸的方式，判斷某個結點的平衡因子（左右子樹高度差）是否大于1，若平衡因子大于1，則其一定不是平衡二叉樹，否則，繼續判斷。

code

/*** Definition of TreeNode:* class TreeNode {* public:* int val;* TreeNode *left, *right;* TreeNode(int val) {* this->val = val;* this->left = this->right = NULL;* }* }*/ class Solution { public:/*** @param root: The root of binary tree.* @return: True if this Binary tree is Balanced, or false.*/bool isBalanced(TreeNode *root) {// write your code here// write your code herereturn isSubTreeBalanced(root) != -1;}int isSubTreeBalanced(TreeNode *root) {if(root == NULL) {return 0;}int left = isSubTreeBalanced(root->left);int right = isSubTreeBalanced(root->right);if(left == -1 || right == -1 || abs(left - right) > 1) {return -1;}else {return (left > right ? left : right) + 1;}} };

轉載于:https://www.cnblogs.com/libaoquan/p/7150116.html

總結

以上是生活随笔為你收集整理的lintcode-93-平衡二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。