二刷 05/2022
Version #1 Top-down version (worse)
Time O(nlogn)
Space O(n) The recursion stack may contain all nodes if the tree is skewed.
Runtime: 2 ms, faster than 26.81% of Java online submissions for Balanced Binary Tree.
Memory Usage: 44.6 MB, less than 34.01% of Java online submissions for Balanced Binary Tree.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
// Top-down recursion
// create a height function
// Each level takes O(n) time to proceed
// Worst case time complexity:
// O(n) + 2 * O(n/2) + 4 * O(n / 4) + ...
// = O(nlogn)
// In a skewed-tree, the algorithm is O(n) since it only checks the height of the first two subtrees
if (root == null) {
return true;
}
return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
private int height(TreeNode node) {
if (node == null) {
return 0;
}
return 1 + Math.max(height(node.left), height(node.right));
}
}
Version #2 Bottom-up (better)
Time O(n) - each node is visited twice
Space O(n)
Runtime: 1 ms, faster than 95.05% of Java online submissions for Balanced Binary Tree.
Memory Usage: 41.6 MB, less than 96.98% of Java online submissions for Balanced Binary Tree.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
class TreeInfo {
public int height;
public boolean isBalanced;
public TreeInfo(int height, boolean isBalanced) {
this.height = height;
this.isBalanced = isBalanced;
}
}
public boolean isBalanced(TreeNode root) {
TreeInfo info = isBalancedHelper(root);
return info.isBalanced;
}
private TreeInfo isBalancedHelper(TreeNode node) {
if (node == null) {
return new TreeInfo(0, true);
}
TreeInfo leftInfo = isBalancedHelper(node.left);
if (!leftInfo.isBalanced) {
return new TreeInfo(-1, false);
}
TreeInfo rightInfo = isBalancedHelper(node.right);
if (!rightInfo.isBalanced) {
return new TreeInfo(-1, false);
}
boolean isBalanced = Math.abs(leftInfo.height - rightInfo.height) <= 1;
if (!isBalanced) {
return new TreeInfo(-1, isBalanced);
}
return new TreeInfo(1 + Math.max(leftInfo.height, rightInfo.height), isBalanced);
}
}
一刷
Every node is visited twiceTotal time O(#nodes)
69.68 %
public class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
return isBalancedHelper(root) != -1;
}
public int isBalancedHelper(TreeNode root) {
//-1 represents that the subtree is not balanced
if (root == null) return 0;
int left = isBalancedHelper(root.left);
int right = isBalancedHelper(root.right);
if (left == -1 || right == -1 || Math.abs(left - right) > 1) return -1;
return Math.max(left, right) + 1;
}
}
No comments:
Post a Comment