1 題目

判斷給定的二叉樹是否是平衡二叉樹

平衡二叉樹的性質為:?要么是一棵空樹，要么任何一個節點的左右子樹高度差的絕對值不超過 1。

一顆樹的高度指的是樹的根節點到所有節點的距離中的最大值。

2 解法

2.1 多次遞歸

最初的想法肯定是先求出每個節點的左右子樹的高度,如果差距不超過1再用遞歸的方式判斷其左右子節點是否平衡.而求高度的方法也用遞歸的方法,所以需要用到多重遞歸:

/*** struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/class Solution { public:/*** * @param root TreeNode類 * @return bool布爾型*/bool isBalanced(TreeNode* root) {// write code hereif (root) {if (abs(height(root->left) - height(root->right)) <= 1) {return (isBalanced(root->left) && isBalanced(root->right));} else {return false;}}return true;}int height(TreeNode* root) {int h = 0;if (root) {int l = height(root->left);int r = height(root->right);h = 1 + (l > r ? l : r);}return h;} };

本來以為性能會很差,結果還可以:

總結

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

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