劍指offer 平衡二叉樹

2022-11-24 15:31:29 字數 1046 閱讀 2689

題目:輸入一棵二叉樹,判斷該二叉樹是否是平衡二叉樹。

分析:首先理解什麼是平衡二叉樹。平衡二叉樹具有以下性質:它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1,並且左右兩個子樹都是一棵平衡二叉樹。

很明顯可以用遞迴解決。

解法一:

1

class

solution

7int left = depth(proot->left);

8int right = depth(proot->right);

9return max(left, right) + 1;10

}11bool isbalanced_solution(treenode*proot)

15int left = depth(proot->left);

16int right = depth(proot->right);

17return (abs(left - right) <= 1 && isbalanced_solution(proot->left) && isbalanced_solution(proot->right));18}

19 };

上述解法的不足在於在計算上層節點的時候,他會反覆計算下層節點的深度,增加了時間複雜度,於是有了後序遍歷的解法,先判斷兩個子樹是否為平衡二叉樹,是的話返回深度,否則標記為1.

解法二:後序遍歷

1

class

solution

7int left = getdepth(proot->left);

8if (left == -1

) 11

int right = getdepth(proot->right);

12if (right == -1

) 15

return abs(left - right) > 1 ? -1 : 1 +max(left, right);16}

17public:18

bool isbalanced_solution(treenode*proot)

21 };

劍指 Offer 55 II 平衡二叉樹

使用遞迴編寫一個求高度的函式,之後使用先序遍歷每個結點,判斷左右子樹的高度差是否滿足要求。這種方法每次判斷一個結點都需要使用遞迴先求出其左右子樹的高度,比如下面這棵樹,判斷1的時候,使用遞迴求了2,3,4的高度,判斷2的時候,又遞迴求了3,4,的高度,這樣就重複求了很多次,產生了很多重疊子問題。所以...

劍指offer系列 39 平衡二叉樹

q 輸入一棵二叉樹,判斷該二叉樹是否是平衡二叉樹。a 結合上一題的計算樹的高度。bool isbalanced solution treenode proot if proot nullptr return true int l treedepth proot left int r treedept...

劍指offer 39 是否為平衡二叉樹

39.是否為平衡二叉樹 輸入一棵二叉樹,判斷該二叉樹是否是平衡二叉樹任意結點的左右子樹高度差不大於1就是平衡二叉樹。1 class solution 8 前序遞迴遍歷 9int preorder treenode proot 17return0 18 1920 leetcode執行時間為1ms,空間...