前言
今天的題目
每天的題目見github(看最新的日期):
https://github.com/gzc426
具體的題目可以去牛客網對應專題去找。
題目
每天一道劍指offer-平衡二叉樹
輸入一棵二叉樹，判斷該二叉樹是否是平衡二叉樹。
https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13&tqId=11192&tPage=2&rp=2&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking
思路
從下往上遍歷，如果子樹是平衡二叉樹，則返回子樹的高度；如果發現子樹不是平衡二叉樹，則直接停止遍歷，這樣至多隻對每個結點訪問一次。
題目詳解
<code>public class Solution {
private boolean flag = true;
public boolean IsBalanced_Solution(TreeNode root) {
TreeLength(root);
return flag;
}
private int TreeLength(TreeNode root)
{
if(root == null)
return 0;
int left = TreeLength(root.left);//左子樹的高度
int right = TreeLength(root.right);//右子樹的高度
if(left-right >= 2 || right - left >= 2)
{//左右子樹高度差大於等於2，標記就不是true
flag = false;
}
return left>right?(left+1):(right+1);
}
}/<code>結束語
作者喬戈裡親歷2019秋招，哈工大計算機本碩，百度java工程師，歡迎大家關注我的微信公眾號：程序員喬戈裡，公眾號有3T編程資源，以及我和我朋友（百度C++工程師）在秋招期間整理的近200M的面試必考的java與C++面經，並有每天一道leetcode打卡群與技術交流群，歡迎關注。
分享到:
閱讀更多 程序員喬戈裡 的文章
