題目描述
輸入一棵二叉樹，判斷該二叉樹是否是平衡二叉樹。
解析：平衡二叉樹具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。所以我們可以求出根節點，左右子樹的深度，并利用它來判定以當前結點為根的樹是不是平衡二叉樹，同時我們考慮用后序遍歷，因為這樣子可以讓我們對每個結點做到只遍歷一次。
代碼如下：
PRivate boolean isBalanced=true; public boolean IsBalanced_Solution(TreeNode root) { getDepth(root); return isBalanced; } public int getDepth(TreeNode root){ if(root==null) return 0; int left=getDepth(root.left); int right=getDepth(root.right); if(Math.abs(left-right)>1){ isBalanced=false; } return right>left ?right+1:left+1; }新聞熱點
疑難解答
