Shulou(Shulou.com)06/03 Report--

This article mainly explains "how to use LeetCode binary tree". The content of the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "how to use LeetCode binary tree".

Tree

First of all, let's see what a tree is.

As shown in the figure, this structure with nodes is a tree.

A tree is a finite set of n (n > = 0) nodes.

Where:

Each element is called a node

The previous section is the parent node of the next section, for example, 1 is the parent node of 2

The uppermost node, that is, the node without a parent, is called the root node, such as 1

A node with the same parent node is called a sibling node, for example, 2,3,4 are sibling nodes.

A node without child nodes is called a leaf node.

Binary tree

It is easy to understand the name, that is, there are two forked trees in each node. However, it is not necessary to have two nodes, as long as it is less than or equal to 2 nodes.

Like this:

Among them, we can see that each node of the green tree has two left and right nodes, and this kind of binary tree is called full binary tree.

There is also a binary tree called a complete binary tree.

Complete binary tree: a binary tree with n nodes is numbered by layer, if the number is I (1 = 2 ^ (x Mel 1) x = log2 (n = 1)

So the height (number of layers) of a binary tree close to balance is close to that of logn.

So the total time complexity is O (nlogn).

Space complexity

Because recursion is used, stack frames are used, which is proportional to the maximum recursive depth, so the space complexity is O (n).

Solution 2

Is there a better solution?

What we used just now is preorder traversal, but we can find that each node will calculate the depth, and there will be a lot of repeated calculations, so we can try a non-repetitive algorithm. Such as direct post-order traversal.

Post-order traversal: for any node, the left subtree is processed first, then the right subtree, and finally the node itself.

The previous method is still used to calculate the depth:

Private int depth (TreeNode root) {if (root = = null) return 0; int left = recur (root.left); int right = recur (root.right); return Math.max (left, right) + 1;}

If we can calculate the depth of the left subtree and the depth of the right subtree, then we can compare it directly. If we find that the difference between the depth of the left subtree and the right subtree of a node is greater than 1, then we can directly return false.

Therefore, the comprehensive solution can be obtained as follows:

Class Solution {public boolean isBalanced (TreeNode root) {return recur (root)! =-1;} private int recur (TreeNode root) {if (root = = null) return 0; int left = recur (root.left); if (left =-1) return-1; int right = recur (root.right); if (right = =-1) return-1; return Math.abs (left-right) < 2? Math.max (left, right) + 1:-1;}} time complexity

N is the total node, traversing all nodes, so the time complexity is O (n).

Space complexity O (n) Thank you for your reading, the above is the content of "how to use LeetCode binary tree". After the study of this article, I believe you have a deeper understanding of how to use LeetCode binary tree, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.