一、题目描述
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
示例 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 。
限制：
0 <= 树的结点个数 <= 10000
二、Java代码实现
1、自顶向下的递归
保证自己满足左右子树深度差小于1的同时，自己的左子树和右子树也满足这个条件。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isBalanced(TreeNode root) { if(root==null){ return true; } return (Math.abs(dfs(root.left)-dfs(root.right))<=1 && isBalanced(root.left) && isBalanced(root.right)); } int dfs(TreeNode node){ if(node == null){ return 0; } int left = dfs(node.left); int right = dfs(node.right); return Math.max(left, right)+1; } }
2、自底向上的递归
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isBalanced(TreeNode root) { return dfs(root)>=0; } int dfs(TreeNode node){ if(node == null){ //叶子节点为深度为0 return 0; } int left = dfs(node.left); int right = dfs(node.right); if(left==-1 || right==-1 || Math.abs(left-right)>1){ //有深度差不满足的，就直接将-1传递上去 return -1; } else { //深度差满足，就将深度传上去 return Math.max(left, right)+1; } } }
