自底向上
其实可以直接在求高度的同时,直接判断即可。
利用后序遍历:左子树、右子树、根节点,可以先递归到叶子节点,然后在回溯的过程中来判断是否满足条件。
时间复杂度:O(n)
空间复杂度:O(n)
public class Solution { public boolean IsBalanced_Solution(TreeNode root) { return depth(root) != -1; } public int depth(TreeNode root) { if (root == null) { return 0; } int left = depth(root.left); if (left == -1) { return -1; } int right = depth(root.right); if (right == -1) { return -1; } if (left - right < (-1) || left - right > 1) { return -1; } else { return 1 + (left > right ? left : right); } } }