剑指Offer——II.平衡二叉树(JS实现) |刷题打卡

我心飞翔 分类:javascript

前言

掘金团队号上线,助你 Offer 临门! 点击 查看详情

题目描述

剑指Offer——II.平衡二叉树(JS实现) |刷题打卡

解题思路

  • 这道题属于二叉树考查深度的问题
  • 本题的核心在于知道二叉树的深度怎么求:二叉树的深度 = 左子树的深度与右子树的深度中的最大值 + 1,这是核心解题点

解题代码

var isBalanced = function(root) {
    let flag = true;
    dfs(root);
    return flag;
    function dfs(root) {
        if (!root) return 0;
        let l = dfs(root.left);
        let r = dfs(root.right);
        if (Math.abs(l - r) > 1) {
            flag = false;
        }
        return Math.max(l,r) + 1;
    }
};
 

总结

  • 本题给我们的启示就是二叉树的深度怎么求:
  • 左子树与右子树中选最大的那个+1就是目标节点的深度。

回复

我来回复
  • 暂无回复内容