牛客題霸 [平衡二叉樹] C++題解/答案

題目描述

輸入一棵二叉樹，判斷該二叉樹是否是平衡二叉樹。

在這里，我們只需要考慮其平衡性，不需要考慮其是不是排序二叉樹

題解：

今天上數據結構剛考了平衡二叉樹
平衡二叉樹定義(AVL)：它或者是一顆空樹，或者具有以下性質的二叉排序樹：它的左子樹和右子樹的深度之差(平衡因子)的絕對值不超過1，且它的左子樹和右子樹都是一顆平衡二叉樹。
所以我們要計算出深度
深度就不斷遞歸左右子樹取最大即可
深度：max(deep(root->left),deep(root->right))+1

代碼：

class Solution { public:int deep(TreeNode*root){if(!root)return 0;return max(deep(root->left),deep(root->right))+1;}bool IsBalanced_Solution(TreeNode* pRoot) {if(!pRoot)return 1;if(IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right)&&abs(deep(pRoot->left)-deep(pRoot->right))<=1)return 1;else return 0;} }; 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的牛客题霸 [平衡二叉树] C++题解/答案的全部內容，希望文章能夠幫你解決所遇到的問題。

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