欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指Offer(39):平衡二叉树

程序员文章站 2022-07-10 13:28:36
...

一、题目描述

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


二、解题思路

使用后序遍历,遍历二叉树的每一个结点,在遍历某个结点之前已经遍历了它的左右子树,如果已经非平衡可以提前退出判断。
在遍历过程中,只需要记录每个结点的深度(深度等于它到叶结点的路径的长度),便可以在遍历的同时判断结点是否平衡。

例如:
   [1]
  [2] [3]
 [4]
[5]
结点5左右子树深度差为0,返回它的深度max(0,0)+1=1
   [1]
  [2] [3]
 [4]
[5]
结点4左右子树深度差为(1-0=1),返回它的深度max(1,0)+1=2
   [1]
  [2] [3]
 [4]
[5]
结点2左右子树深度差为(2-0=2),超过1,返回-1,表明不平衡,退出递归


三、编程实现

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return getDepth(root) != -1;
    }

    private int getDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 左子树的深度
        int left = getDepth(root.left);
        // 如果左子树不平衡直接返回-1,表明该树不平衡
        if (left == -1) {
            return -1;
        }
        // 右子树的深度
        int right = getDepth(root.right);
        // 如果右子树不平衡直接返回-1,表明该树不平衡
        if (right == -1) {
            return -1;
        }
        // 如果左右子树深度差超过1,则返回-1,表明该树不平衡;
        // 如果深度差小于等于1,则返回当前结点的深度
        return Math.abs(left - right) > 1 ? -1 : (1 + Math.max(left, right));
    }
}