商城网站建设合同参考消息今天新闻

题目来源
110. 平衡二叉树

题目分析

平很二叉树:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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;}
}

题外话

很多初学者会在想，不要这个判断行不行，或者这个判断的意义是什么

我们先去掉两个if运行

当发现一个节点为-1(第二行)，那么递归会回到递归初始，一直为-1然后进行if判断直接返回-1结果，结束了本次方法，右孩子就可以不用判断了