How to Check if a Binary Tree is Balanced (Top-down and Bottom-u
- 时间:2020-09-18 17:26:09
- 分类:网络文摘
- 阅读:115 次
Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as: a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example 1:
Given the following tree [3,9,20,null,null,15,7]:3 / \ 9 20 / \ 15 7Return true.
Example 2:
Given the following tree [1,2,2,3,3,null,null,4,4]:
1 / \ 2 2 / \ 3 3 / \ 4 4Return false.
Most of the Binary tree problems can be tackled by Recursion – because the tree itself is defined recursively. Depending on the directions, we can perform recursions either top-down (from the root to the leaves) or the bottom-up (from the leaves to the root). In this particular problem, the bottom-up approach is more efficient as the depths of the trees are passed up without duplicate computation efforts.
Top-Down Recursion Algorithm to Validate a Balanced Binary Tree by Checking the Depths
We first define a recursive function to get the depth of a binary tree. Then, at each node from root to the leaves, we check if the depth of its left branch and the right subtree is no more than 1 difference. Then, we also need to recursively check if the sub-trees are balanced.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isBalanced(TreeNode* root) { if (!root) return true; int left = maxDepth(root->left); int right = maxDepth(root->right); if (abs(left - right) > 1) return false; return (isBalanced(root->left) && isBalanced(root->right)); } private: int maxDepth(TreeNode* root) { if (!root) return true; return max(maxDepth(root->left), maxDepth(root->right)) + 1; } }; |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isBalanced(TreeNode* root) { if (!root) return true; int left = maxDepth(root->left); int right = maxDepth(root->right); if (abs(left - right) > 1) return false; return (isBalanced(root->left) && isBalanced(root->right)); } private: int maxDepth(TreeNode* root) { if (!root) return true; return max(maxDepth(root->left), maxDepth(root->right)) + 1; } };
The time complexity is O(N^2) as at each node, the depths are recalculated repeatedly. It is worse when the binary tree is degenerated into a linked-list.
Bottom-up Recursion Algorithm to Validate a Balanced Binary Tree by Passing Up the Depths
We can compute the depth for the binary sub-tree, and pass it up. If the tree is un-balanced, we pass the value as -1, then we don’t need to re-calculate the depths for a upper-level nodes (parent nodes) because the entire tree will be un-balanced anyway.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isBalanced(TreeNode* root) { return depth(root) != -1; } private: int depth(TreeNode* root) { if (root == nullptr) return 0; int left = depth(root->left); if (left == -1) return -1; int right = depth(root->right); if (right == -1) return -1; if (abs(left - right) > 1) return -1; return max(right, left) + 1; } }; |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isBalanced(TreeNode* root) { return depth(root) != -1; } private: int depth(TreeNode* root) { if (root == nullptr) return 0; int left = depth(root->left); if (left == -1) return -1; int right = depth(root->right); if (right == -1) return -1; if (abs(left - right) > 1) return -1; return max(right, left) + 1; } };
The time complexity is improved from O(N^2) to O(N). Both recursion approaches require O(N) stack space.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:3 Incredible Landing Pages And What We Can Learn From Them What is Cycle Counting and How to Implement It in Your Retail Bu 4 Reasons Why Your Blog is Struggling to Find an Audience 6 Best Fashion Bloggers for Style Inspiration The Strategy You Need to Write Better Blog Posts Than Your Compe How to Improve Your Blog’s Bounce Rate (and Why You Should) Does Your SME Have A Disaster Recovery Plan? 7 Best SEO Trends Gaining Popularity In 2019 How To Choose The Best Hosting Service For A WordPress Website An Idiot’s Guide to Email Automation for Bloggers
- 评论列表
-
- 添加评论