leetcode面试题55平衡二叉树

面试题55 - II. 平衡二叉树

难度简单27

输入一棵二叉树的根节点&＃xff0c;判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1&＃xff0c;那么它就是一棵平衡二叉树。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

3/ \9 20/ \15 7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

1/ \2 2/ \3 3/ \4 4

返回 false 。

限制&＃xff1a;

• 1 <&＃61; 树的结点个数 <&＃61; 10000

这个题思路&＃xff0c;首先写方法求解树的深度&＃xff0c;这里可以递归&＃xff0c;也可以借助队列进行层次遍历。

然后在对树的每个节点的左右子节点做判断&＃xff0c;判断当前节点是否满足平衡二叉树的要求条件。

从顶向下进行遍历&＃xff0c;这样的方法存在缺点&＃xff1a;存在大量重复的计算&＃xff0c;效率低下。

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val &＃61; x; }* }*/
class Solution {//从根节点向下遍历每个节点 判断当前节点是否满足深度差不超过1的条件//这样子存在大量重复的遍历 效率低下public boolean isBalanced(TreeNode root) {if(root&＃61;&＃61;null) return true;// return isBalanced(root.left)&&isBalanced(root.right);if(Math.abs(getDepth(root.left)-getDepth(root.right))>1) reuturn false;return isBalanced(root.left)&&isBalanced(root.right);}//递归法求解树的深度public int getDepth(TreeNode root){if(root&＃61;&＃61;null) return 0;int left &＃61;getDepth(root.left);int right &＃61;getDepth(root.right);return Math.max(left,right)&＃43;1;}
}

考虑自底向上&＃xff0c;后序遍历&＃43;剪枝&＃xff0c;不满足条件时直接返回-1。

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val &＃61; x; }* }*/
class Solution {//自底向上 后序遍历&＃43;减枝public boolean isBalanced(TreeNode root) {return isBalancedHelper(root)!&＃61;-1;}public int isBalancedHelper(TreeNode root){if(root&＃61;&＃61;null) return 0;int left &＃61;isBalancedHelper(root.left);if(left&＃61;&＃61;-1) return -1;int right &＃61;isBalancedHelper(root.right);if(right&＃61;&＃61;-1) return -1;return Math.abs(right-left)<2?Math.max(right,left)&＃43;1:-1;}
}