How to realize balanced binary Tree in C++
This article introduces the knowledge of "how to achieve a balanced binary tree in C++". In the operation of practical cases, many people will encounter such a dilemma. Then let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!
Balanced binary tree
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 everynode never differ by more than 1.
Example 1:
Given the following tree [3,9,20,null,null,15,7]:
three
/
9 20
/
15 7
Return true.
Example 2:
Given the following tree [1,2,2,3,3,null,null,4,4]:
one
/
2 2
/
3 3
/
4 4
Return false.
To find out whether the binary tree is balanced or not, according to the definition in the topic, a highly balanced binary tree means that the depth difference between the two subtrees of each node cannot exceed 1, so we definitely need a function to find the depth of each node, and then compare the depth difference between the two subtrees of each node. The time complexity is O (NlgN). The code is as follows:
Solution 1:
Class Solution {public: bool isBalanced (TreeNode * root) {if (! root) return true; if (abs (getDepth (root- > left)-getDepth (root- > right)) > 1) return false; return isBalanced (root- > left) & & isBalanced (root- > right);} int getDepth (TreeNode * root) {if (! root) return 0; return 1 + max (getDepth (root- > left), getDepth (root- > right)) }}
The above method is correct but not very efficient, because each point will be visited once when the above point calculates the depth, and we can optimize it. The method is that if we find that the subtree is unbalanced, we do not calculate the specific depth, but return-1 directly. Then the optimized method is as follows: for each node, we recursively obtain the depth of the left and right subtrees through the checkDepth method. If the subtree is balanced, the real depth is returned. If the subtree is not balanced, it directly returns-1. The time complexity of this method is O (N) and the space complexity is O (H). See the code as follows:
Solution 2:
Class Solution {public: bool isBalanced (TreeNode * root) {if (checkDepth (root) = =-1) return false; else return true;} int checkDepth (TreeNode * root) {if (! root) return 0; int left = checkDepth (root- > left); if (left = =-1) return-1; int right = checkDepth (root- > right); if (right = =-1) return-1 Int diff = abs (left-right); if (diff > 1) return-1; else return 1 + max (left, right);}}; this is the end of the introduction of "how C++ achieves a balanced binary tree". Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!
