剑指offer T 55-|| 平衡二叉树

case1:暴力法：每次去求取root的左右子树的高度差，符合条件后再去判定root.left以及root.right是否为平衡二叉树

class Solution { public int NodeDepth(TreeNode root){ if(root==null) return 0; return Math.max(NodeDepth(root.left),NodeDepth(root.right))+1; } public boolean isBalanced(TreeNode root) { if(root==null||root.left==null&&root.right==null) return true; int leftDepth = NodeDepth(root.left); int rightDepth = NodeDepth(root.right); return Math.abs(leftDepth-rightDepth)<=1&&isBalanced(root.left)&&isBalanced(root.right); } }

针对case1存在的重复计算问题，我们可以这么做利用后续遍历，在求每个结点的高度的同时，判定其是否为平衡的，这样就避免了重复计算问题 时间复杂度为O(n),空间复制度O(n)

class Solution { public int NodeDepth(TreeNode root){ if(root==null) return 0; int leftDepth = NodeDepth(root.left); int rightDepth = NodeDepth(root.right); //当左右子树是平衡的且以root为根节点的子树也是平衡的时才返回其高度 if(leftDepth>=0&&rightDepth>=0&&Math.abs(leftDepth-rightDepth)<=1){ return Math.max(leftDepth,rightDepth)+1; } //否则表示以root为根节点的子树不是平衡的，直接return -1 return -1; } public boolean isBalanced(TreeNode root) { if(root==null||root.left==null&&root.right==null) return true; return NodeDepth(root)>=0; } }