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

• 2019 年 10 月 4 日
• 笔记

前言

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