輸入一棵二叉樹，判斷該二叉樹是否是平衡二叉樹，在這里，我們只需要考慮其平衡性，不需要考慮其是不是排序二叉樹
解題思路
最直接的做法，遍歷每個結點，借助一個獲取樹深度的遞回函式，根據該結點的左右子樹高度差判斷是否平衡，然后遞回地對左右子樹進行判斷，
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root == null) {
return true;
}
return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1
&& IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
}
private int maxDepth(TreeNode node) {
if(node == null) {
return 0;
}
return Math.max(1 + maxDepth(node.left), 1 + maxDepth(node.right));
}
}
這種做法有很明顯的問題，在判斷上層結點的時候，會多次重復遍歷下層結點，增加了不必要的開銷，如果改為從下往上遍歷，如果子樹是平衡二叉樹，則回傳子樹的高度；如果發現子樹不是平衡二叉樹，則直接停止遍歷，這樣至多只對每個結點訪問一次，
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root == null) {
return true;
}
return getDepth(root) != -1;
}
private int getDepth(TreeNode node) {
if(node == null) {
return 0;
}
int left = getDepth(node.left);
if(left == -1) {
return -1;
}
int right = getDepth(node.right);
if(right == -1) {
return -1;
}
return Math.abs(left - right) <= 1 ? Math.max(left, right) + 1 : -1;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/184383.html
標籤：其他
上一篇：丁磊建議將少兒編程納入學業水平考試，網友炸開了鍋！家長們早已心知肚明！
下一篇：selenium~使用unittest測驗框架,批量執行測驗腳本,addTest、makeSuite、TestLoader、discover的使用