平衡二叉樹

題目

思路與代碼實現

常規解法：

 int max(int a,int b){return a>b?a:b;}int maxDepth(struct TreeNode* root) 
{if(root==NULL)return 0;return 1+max(maxDepth(root->left),maxDepth(root->right));
}bool isBalanced(struct TreeNode* root) 
{if(root==NULL)return true;if(abs(maxDepth(root->left)-maxDepth(root->right))>=2)return false;return isBalanced(root->left)&&isBalanced(root->right);
}

常規解法雖然能解決問題，但是仔細地看，該算法時間復雜度達到了O(N*N)。

主要原因是重復步驟太多，可以看出該遍歷方式是前序遍歷，我們每次比較當前高度差是否符合“平衡”時，都需要層層計算其子樹高度，這樣當我們再次來算他子樹高度時，有些步驟顯得冗余。

舉個例子：求A的高度就需要求B的高度，求B的高度就需要求C的高度…然后在求B的高度時又需要求C的高度…這樣就做了許多重復工作

所以這個時候我們可以就行后序遍歷，即層遞歸到求葉子結點高度，然后在求完下層高度后在求上層高度，再求上層高度時將下層的高度返回到上層，這樣上層就無需在做一些求下層高度的冗余操作。

具體優化代碼：

int max(int a,int b){return a>b?a:b;}int maxDepth(struct TreeNode* root) 
{if(root==NULL)return 0;return 1+max(maxDepth(root->left),maxDepth(root->right));
}bool _isBalanced(struct TreeNode* root,int* pDepth)
{if(root==NULL){*pDepth=0;return true;}int leftDepth=0;if(_isBalanced(root->left,&leftDepth)==false)return false;int rightDepth=0;if(_isBalanced(root->right,&rightDepth)==false)return false;if(abs(leftDepth-rightDepth)>1)return false;*pDepth=1+max(leftDepth,rightDepth);return true;
}bool isBalanced(struct TreeNode* root) 
{int depth=0;return _isBalanced(root,&depth);
}

此時時間復雜度就達到了O(N)