110. Balanced Binary Tree 发表于 2021-11-15 DFS123456789101112131415161718192021class Solution { public boolean isBalanced(TreeNode root) { if (root == null) { return true; } if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1) { return false; } return isBalanced(root.left) && isBalanced(root.right); } private int getHeight(TreeNode root) { if (root == null) { return 0; } return Math.max(getHeight(root.left), getHeight(root.right)) + 1; }} 该方法最为直观,但是效率较低。 DFS12345678910111213141516171819202122232425262728293031class Solution { public boolean isBalanced(TreeNode root) { return getHeight(root) != -1; } /** * 返回当前二叉树的高度,如果当前二叉树不平衡,则返回 -1 */ private int getHeight(TreeNode node) { if (node == null) { return 0; } int leftHeight = getHeight(node.left); if (leftHeight == -1) { return -1; } int rightHeight = getHeight(node.right); if (rightHeight == -1) { return -1; } int diff = Math.abs(leftHeight - rightHeight); if (diff > 1) { return -1; } else { return Math.max(leftHeight, rightHeight) + 1; // 注意此处返回左右子树较大的高度并加 1, 即加上 root 节点 } }} 自底向上计算,如果遇到不平衡的子树则及时返回。 Reference110. Balanced Binary Tree剑指 Offer 55 - II. 平衡二叉树