当前位置：首页 > news >正文

LeetCode-110. 平衡二叉树

news 2025/7/9 20:20:45

题目分析

平很二叉树:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。
二叉树节点的深度和二叉树节点的高度
在这里插入图片描述

递归法

递归三步曲

1.明确递归函数的参数和返回值

参数：当前传入节点。
返回值：以当前传入节点为根节点的树的高度。
那么如何标记左右子树是否差值大于1呢？
如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。
所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。
代码如下：

int getHeight(TreeNode root)

2.明确终止条件

递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0
代码如下：

        if(root == null){return 0;}

3.明确单层递归的逻辑

如何判断以当前传入节点为根节点的二叉树是否是平衡二叉树呢？当然是其左子树高度和其右子树高度的差值。
分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了。
代码如下：

        int leftHeight = getHeight(root.left);   //左if(leftHeight == -1){return -1;}int rightHeight = getHeight(root.right);   //右if(leftHeight == -1){return -1;}int result;if(Math.abs(leftHeight-rightHeight)>1){        //中return -1;}else{result = Math.max(leftHeight,rightHeight)+1;}return result;

整体递归代码如下：

class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) != -1;}public static int getHeight(TreeNode root){if(root == null){return 0;}int leftHeight = getHeight(root.left);   //左if(leftHeight == -1){return -1;}int rightHeight = getHeight(root.right);   //右if(rightHeight == -1){return -1;}int result;if(Math.abs(leftHeight-rightHeight)>1){        //中return -1;}else{result = Math.max(leftHeight,rightHeight)+1;}return result;}
}