剑指offer_二叉树---平衡二叉树

简介: 剑指offer_二叉树---平衡二叉树

##题目描述

输入一棵二叉树,判断该二叉树是否是平衡二叉树。

##思路

如果每个节点的左右子树的深度相差都不超过1,即最大深度差为1,则可判定为平衡二叉树。

两种思路:

第一种是递归判断每一个根节点,都要求出它的左右子树的深度,深度相差小于1即可(根左右),可以理解为自顶向下。

第二种是从自己的左右子树开始判断用一个数组来记录深度(为防止归零,所以用引用类型)只要自己的左右深度条件都满足,则该树满足,不需要重复计算深度。(左右根),可以理解为自底向上

##代码

第一种思路

/**
 * 
 */
package offerTest;
/**
 * <p>
 * Title:Balance
 * </p>
 * <p>
 * Description:
 * </p>
 * 
 * @author 田茂林
 * @data 2017年8月21日 上午9:45:44
 */
public class Balance {
  public boolean IsBalanced(TreeNode root) {
    if (root == null) { // 递归结束条件
      return true;
    }
    int diff = Math.abs(deep(root.left) - deep(root.right)); // 求绝对值函数
    if (diff > 1) {
      return false; // 如果相差大于1,返回false
    }
    return IsBalanced(root.left) && IsBalanced(root.right); // 递归检查每一个几点
  }
  // 求节点深度函数
  public int deep(TreeNode root) {
    if (root == null) {
      return 0;
    }
    return deep(root.left) > deep(root.right) ? deep(root.left) + 1
        : deep(root.right) + 1;
  }
}

第二种思路:优化算法

/**
 * 
 */
package offerTest;
import 二叉树.TreeNode;
/**
 * <p>
 * Title:Balance
 * </p>
 * <p>
 * Description:
 * </p>
 * 
 * @author 田茂林
 * @data 2017年8月21日 上午9:45:44
 */
public class Balance {
   // 优化算法
  public boolean IsBalancedSuper(TreeNode root) {
    int[] depth = new int[1];
    return isBalance(root, depth);
  }
  public boolean isBalance(TreeNode root, int[] depth) {
    if (root == null) {
      depth[0] = 0;
      return true;
    }
    boolean leftbalance = isBalance(root.left, depth);
    int leftdepth = depth[0];
    boolean rightbalance = isBalance(root.right, depth);
    int rightdepth = depth[0];
    depth[0] = Math.max(leftdepth + 1, rightdepth + 1); // 取二者最大为深度
    return leftbalance && rightbalance
        && Math.abs(rightdepth - leftdepth) < 1; // 如果左右子树都平衡,且相差小于1,则为平衡二叉树
  }
}


相关文章
|
7月前
|
Java BI 数据库管理
二叉树---前,中,后序遍历做题技巧(前,中,后,层次,线索二叉树)
二叉树---前,中,后序遍历做题技巧(前,中,后,层次,线索二叉树)
103 11
|
7月前
|
算法 API DataX
二叉树(下)+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”
二叉树(下)+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”
|
算法 C语言 C++
【树】你真的会二叉树了嘛? --二叉树LeetCode专题Ⅲ
这题算是简单题,我们依然从最简单的情况来考虑。
69 0
|
7月前
|
存储 Serverless 索引
二叉树的前序遍历 、二叉树的最大深度、平衡二叉树、二叉树遍历【LeetCode刷题日志】
二叉树的前序遍历 、二叉树的最大深度、平衡二叉树、二叉树遍历【LeetCode刷题日志】
LeetCode刷题Day14——二叉树(完全二叉树、平衡二叉树、二叉树路径、左叶子之和)
一、完全二叉树的节点个数 题目链接:222. 完全二叉树的节点个数
|
存储 算法 C语言
【树】你真的会二叉树了嘛? --二叉树LeetCode专题Ⅱ
这里有两种方法(深度优先搜索与广度优先搜索)其实也就是前序遍历与层序遍历,层序遍历这里简单提一下.与上面的大同小异就不过多赘述了:依旧是遍历出每一层最大的值,将其放入数组即可.
74 0
剑指offer_二叉树---二叉搜索树的第k个结点
剑指offer_二叉树---二叉搜索树的第k个结点
67 0
剑指offer_二叉树---二叉搜索树的后序遍历
剑指offer_二叉树---二叉搜索树的后序遍历
71 0
剑指offer_二叉树---二叉搜索树与双向链表
剑指offer_二叉树---二叉搜索树与双向链表
66 0
剑指offer_二叉树---重建二叉树
剑指offer_二叉树---重建二叉树
65 0