嗨客网搜索
平衡二叉树

题目

力扣第 110 题,平衡二叉树。给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例1:

22_平衡二叉树.png

输入:root = [3,9,20,null,null,15,7] 输出:true

示例2:

23_平衡二叉树.png

输入:root = [1,2,2,3,3,null,null,4,4] 输出:false

示例3:

输入:root = [] 输出:true

提示:

  • 树中的节点数在范围 [0, 5000]
  • -104 <= Node.val <= 104

思路

本题中,平衡二叉树的特点是每个节点的左右两边子树的高度差不能超过 1,所以最简单有效的办法就是分别求出每个节点的左右子树的高度差。如果高度差大于 1 就返回 false。如果所有的情况下高度差小于等于 1。那么就返回 true。

熟悉树结构的情况都同学都清楚,解决树的遍历就需要用到递归,我们就具体的情况来分析一下。

示例1:遍历 [3,9,20,null,null,15,7] 树结构:

因为使用的是递归调用,判断每一个节点的子树的高度,所以我们会从叶子结点开始,逐个判断其左右节点高度:

24_平衡二叉树.png

这边在计算每个节点的左右节点的高度的时候,是从末节点开始计算。计算步骤如下:

  • 第一步:计算 9 节点的左子树高度 0 ,右子树高度 0。两个高度相差为 0 。符合条件。
  • 第二步:计算 15 节点的高度差,左子树高度 0,右子树高度0。两个高度相差为 0。符合条件。
  • 第三步:计算 7 节点的高度差,左右子树高度都为 0。符合条件
  • 第四步:计算 20 节点的高度差,左子树高度 1,右子树高度 1。两个高度差为 0,符合条件。
  • 第五步:计算 3 节点的高度差,左子树高度 1,右子树高度为 2,两个高度差为 1。符合条件。

因为每个节点的高度差都计算过了,符合条件,所以返回 true。

示例2:遍历[1,2,2,3,3,null,null,4,4] 结构:

25_平衡二叉树.png

和上面的计算步骤一样,也是从底往上计算,分别计算每个节点的左右子树的高度差:

  • 第一步:计算左边的节点 4 的子树高度差,左右节点子树高度都是 0。符合条件。
  • 第二步:计算右边的节点 4 的子树高度差,左右子节点高度都是 0。符合条件。
  • 第三步:计算左边的节点 3 的子树高度差,左右子节点的高度都是 1 ,符合条件。
  • 第四步:计算右边的节点 3 的子树高度差,左右子节点的高度都是 0 ,符合条件。
  • 第五步:计算左边节点 2 的子树高度差,左子节点高度 2,右子节点高度 1,高度差为 1,符合条件。
  • 第六步:计算右边节点 2 的子树高度差,左右节点的高度为 0。高度差为 0,符合条件。
  • 第七步:计算节点 1 的子树高度差,左子节点高度 3,右子节点高度 1,高度差为 2,不符合条件。

在计算最后一个节点的高度差的时候,返回高度差为 2,所以不符合条件,返回 false。

代码具体实现

Java语言版本

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isBalanced(TreeNode root) { if(root == null){ return true; } if(!isBalanced(root.left)){//如果左子树不平衡返回false return false; } if(!isBalanced(root.right)){//如果右子树不平衡返回false return false; } int leftHeight =getHeight(root.left); int rightHeight = getHeight(root.right); if(leftHeight - rightHeight <= 1 && leftHeight - rightHeight >= -1 ){ return true; } return false; } //计算节点高度 private int getHeight(TreeNode node){ if(node == null){ return 0; } int leftheight = getHeight(node.left); int rightHeight = getHeight(node.right); return leftheight > rightHeight ? leftheight + 1 : rightHeight + 1 ; } }

Go语言版本

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func isBalanced(root *TreeNode) bool { if root == nil { return true } if !isBalanced(root.Left) {//如果左子树不平衡返回false return false } if !isBalanced(root.Right) {//如果右子树不平衡返回false return false } leftHeight := getHeight(root.Left) rightHeight := getHeight(root.Right) if leftHeight - rightHeight <= 1 && leftHeight - rightHeight >= -1 { return true } return false } //计算节点高度 func getHeight(node *TreeNode) int{ if node == nil { return 0; } leftheight := getHeight(node.Left) rightHeight := getHeight(node.Right) if leftheight > rightHeight { return leftheight + 1 } else { return rightHeight + 1 } }

赞助商链接:


嗨客网顶部