[leetcode] Balanced Binary Tree | 看一棵二叉树是否balanced
Posted October 7, 2013
on:- In: classic | leetcode
- Leave a Comment
经典题,注意balanced的定义:左右子树都balance,且高度差<=1。所以下面这个也是balanced的,即使a的做右子树都不是完全树。
a / \ b d / \ c e
唯一的trick:不用生成新的data structure来保存“boolean isBalanced, int height”,直接用height = -1表示不平衡就行。
public boolean isBalanced(TreeNode root) { return getHeight(root) >= 0; } private int getHeight(TreeNode root) { if (root == null) return 0; int leftHeight = getHeight(root.left); if (leftHeight < 0) return -1; int rightHeight = getHeight(root.right); if (rightHeight < 0) return -1; if (Math.abs(leftHeight - rightHeight) > 1) return -1; return Math.max(leftHeight, rightHeight) + 1; }
Leave a Reply