Leetcode每日一题之平衡二叉树「简单」

Link

思路

  1. 当且仅当子树都是平衡二叉树时，这个树才是平衡二叉树，明显递归好使
  2. 判断子树高度也需要递归

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
	public boolean isBalanced(TreeNode root) {
		if (root == null) {
			return true;
		}
		return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
	}

	int height(TreeNode node) {
		if (node == null) {
			return 0;
		} else {
			return Math.max(height(node.left), height(node.right)) + 1;
		}
	}
}

优化方向

  1. height函数多次重复调用，可以使用缓存