剑指 Offer — 平衡二叉树

复仇Bytedance之路

题目描述：

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过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 。

限制：

1 <= 树的结点个数 <= 10000

题解

总体思想还是递归，但是同时用到了两个。

/** * 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(treeDepth(root.left) - treeDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); } //这就是一个计算树深度的递归函数，可以记下来 public int treeDepth(TreeNode root){ if(root==null){ return 0; } return Math.max(treeDepth(root.left),treeDepth(root.right))+1; } }

拆开来看看

//这就是一个计算树深度的递归函数，可以记下来 public int treeDepth(TreeNode root){ if(root==null){ return 0; } return Math.max(treeDepth(root.left),treeDepth(root.right))+1; }

这是一个典型的递归求树的深度，递归终止条件即使搜索到空节点。最后一层是max(0,0)+1，然后一层层的往上return。

再来看看另外一个递归：

public boolean isBalanced(TreeNode root) { if(root==null) return true; //注意后两个判断，题目要求的是任意节点的左右子树的深度差，因此对于每一个节点都需要再次判断。 return Math.abs(treeDepth(root.left) - treeDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); }

这个返回的细节太重要了，最开始我就写了return Math.abs(treeDepth(root.left) - treeDepth(root.right)) <= 1，其实这只比较了根节点是否符合条件，并没有将树中的每一个节点都进行判断。