代码随想录算法刷题训练营day17：LeetCode(110)平衡二叉树
LeetCode(110)平衡二叉树
题目
代码
/**
* 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) {
//一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1
if(root==null){
return true;
}
//一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1
//设置一个函数求求左右节点的高度差，并在求的过程中，判断左右节点的高度差
int flagNode=betweenNodeHeight(root);
if(flagNode==-1){
return false;
}else{
return true;
}
}
public int betweenNodeHeight(TreeNode root){
if(root==null){
return 0;
}
//后续遍历，先左子树，再右子树，再根-----一层一层往上返回-1；
int leftHeight=betweenNodeHeight(root.left);
if(leftHeight==-1){
return -1;
}
int rightHeight=betweenNodeHeight(root.right);
if(rightHeight==-1){
return -1;
}
if(Math.abs(leftHeight-rightHeight)>1){
return -1;
}else{
int rootHeight=Math.max(leftHeight, rightHeight)+1;
return rootHeight;
}
}
}
