剑指offer—平衡二叉树 解答

剑指offer—平衡二叉树

题目描述

给定一个二叉树,判断它是否是高度平衡的二叉树。

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
返回 false 。

思路

  • 递归

我们需要保存每个左右子树节点的深度,然后进行比较,我们使用一个全局boolean变量flag接收返回值(递归要返回深度),比较时如果左右子树相差大于1,则说明不是平衡二叉树,把flag置为false,递归结束后返回flag

  1. 递归出口:

    节点为空,返回当前节点深度

  2. 递归返回:

    当前节点左右子树深度的最大值,用于下一次与兄弟节点进行比较

  3. 递归获取左右子树节点深度:

    如果左或右节点为空,则递归使用深度+1就不对,要使用当前深度

int l = dfs(node.left,node.left!=null?height+1:height);
int r = dfs(node.right,node.right!=null?height+1:height);
  1. 使用Math.abs()获取高度差,>1则把flag置为false
if(Math.abs(l-r)>1) flag = false;

代码

public class Solution {
    boolean flag = true;
    public boolean IsBalanced_Solution(TreeNode root) {
        dfs(root,0);
        return flag;
    }
    public int dfs(TreeNode node,int height){
        if(node==null) return height;
        int l = dfs(node.left,node.left!=null?height+1:height);
        int r = dfs(node.right,node.right!=null?height+1:height);
        if(Math.abs(l-r)>1) flag = false;
        return Math.max(l,r);
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/balanced-tree.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!