leetcode balanced binary tree(看不懂...)

本文主要是介绍leetcode balanced binary tree(看不懂...)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://www.cnblogs.com/Antech/p/3705928.html

问题：给一个二叉树，写一个算法判断这个树是不是balanced。

Solution #1.

第一次遇到这个问题时我的解法，如下：

public class Solution {public boolean isBalanced(TreeNode root) {if(root == null){return true;}int depthOfLeft = getDepth(root.left, 1);int depthOfRight = getDepth(root.right, 1);if(Math.abs(depthOfRight-depthOfLeft) > 1){return false;}else{return isBalanced(root.left) && isBalanced(root.right);}}private int getDepth(TreeNode tree, int currentDepth){if(tree == null){return currentDepth;}return Math.max(getDepth(tree.left, currentDepth+1), getDepth(tree.right, currentDepth+1));}
}

写了一个getDepth()函数，访问每个节点都要调用一次这个函数。这个Solution也通过了leetcode的验证程序，但是后来想了想，I can do better.

下面是我对此算法时间复杂度的分析，当整棵树有N个节点时，时间复杂度是O(N*logN).

Solution #2:

今天我想出了更好的Solution，只需一遍DFS，可以将时间复杂度优化到O(N)，但是空间复杂度同样是O(N).

public class CheckTreeBalanced {HashMap<TreeNode, Integer> heights = new HashMap<TreeNode, Integer>();// The idea is to run DFS onceboolean isBalanced(TreeNode root){if(root == null){heights.put(null, 0);return true;}if( isBalanced(root.left) && isBalanced(root.right) ){if(Math.abs(heights.get(root.left) - heights.get(root.right)) > 1){return false;}else{int currentHeight = Math.max(heights.get(root.left),heights.get(root.right)) + 1;heights.put(root, currentHeight);return true;}}else{return false;}}
}

Solution #3:

Cracking the coding interview上看到另一种解法，time complexity O(N), space complexity O(logN). 之所以占用logN的空间是因为这是DFS的特点，整棵树的高度H=logN，DFS必然会占用O(H), explicitly or implicitly.

该算法的思路是基于Solution #1的一种改进，把每个节点的height信息和isBalanced信息融合到一起个变量中：

如果该变量>=0，那么该节点是balanced并且该变量就是节点的height；

如果该变量<0，那么该节点是unbalanced，但同时我们失去了它的height信息。

public class CheckTreeBalanced2 {public int checkHeight(TreeNode root){if(root == null){return 0;}int leftHeight = checkHeight(root.left);if(leftHeight == -1){return -1;}int rightHeight = checkHeight(root.right);if(rightHeight == -1){return -1;}int heightDiff = leftHeight - rightHeight;if(Math.abs(heightDiff) > 1){return -1;}else{return Math.max(leftHeight, rightHeight);}}public boolean isBalance(TreeNode root){if(checkHeight(root) == -1){return false;}else{return true;}}
}