每天一道剑指offer-平衡二叉树

前言

今天的题目
每天的题目见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

思路

• 从下往上遍历，如果子树是平衡二叉树，则返回子树的高度；如果发现子树不是平衡二叉树，则直接停止遍历，这样至多只对每个结点访问一次。

题目详解

 
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);
    }
}
 

结束语

作者乔戈里亲历2019秋招，哈工大计算机本硕，百度java工程师，欢迎大家关注我的微信公众号：程序员乔戈里，公众号有3T编程资源，以及我和我朋友（百度C++工程师）在秋招期间整理的近200M的面试必考的java与C++面经，并有每天一道leetcode打卡群与技术交流群，欢迎关注。