Shulou(Shulou.com)05/31 Report--

This article mainly introduces the relevant knowledge of "how to solve the C language balanced binary tree problem". The editor shows you the operation process through an actual case, and the operation method is simple, fast and practical. I hope this article "how to solve the C language balanced binary tree problem" can help you solve the problem.

Description of the topic

Given a binary tree, determine whether it is a highly balanced binary tree.

In this problem, a highly balanced binary tree is defined as: the absolute value of the height difference between the left and right subtrees of each node of a binary tree is not more than 1.

Second, the way to solve the problem

A binary tree is a balanced binary tree if and only if all its subtrees are also balanced binary trees, so we use recursion to determine whether all its subtrees are balanced binary trees.

Top-down recursion (violent solution)

Top-down is similar to preorder traversal, first judging whether the current tree is balanced, and then judging whether the left and right subtrees of the current tree are balanced.

Core ideas

Write two functions:

Subfunction: calculate the height of any current node (tree) root root is empty node: Depth (root) = 0root is not empty node: Depth (root) = max (Depth (root- > left), Depth (root- > right)) + 1

Main function: recursively traverses all the subtrees of root in turn. For the "currently traversed subtrees", to judge whether it is balanced or not, first calculate the height of the left and right subtrees, and then determine whether the height difference is less than 1.

If you do not exceed it, you can continue to recursively traverse the "left and right subtrees of the current tree" to determine whether it is balanced.

If it exceeds 1, it means that the balance condition is not met, then false is returned directly without recursion.

Recursive process demonstration: top-down recursion is similar to preorder traversal

/ * Definition for a binary tree node. * struct TreeNode {* int val; * struct TreeNode* left; * struct TreeNode* right; *}; * / / calculate the height of any current node (tree) (subfunction) int TreeDepth (struct TreeNode* root) {/ / the current node is empty if (root = = NULL) {return 0 } / / if the current node is not empty, calculate the height of its left and right subtrees int leftDepth = TreeDepth (root- > left); int rightDepth = TreeDepth (root- > right); / / the height of the current node (tree) return leftDepth > rightDepth? LeftDepth + 1: rightDepth + 1;} bool isBalanced (struct TreeNode* root) {/ / recursively traverses all the subtrees of root, judging whether the current subtree is a highly balanced binary tree / / the root node of the current tree is empty, indicating that it satisfies the highly balanced binary tree and returns true if (root = = NULL) {return true } / / if the root node of the current tree is not empty, calculate the height of its left and right subtrees int leftDepth = TreeDepth (root- > left); int rightDepth = TreeDepth (root- > right); / / calculate the height difference between the left and right subtrees int ret = leftDepth > rightDepth? LeftDepth-rightDepth: rightDepth-leftDepth; / / height difference is less than 1 before you can continue recursively traversing the left and right subtrees of the current tree, return ret left) & & isBalanced (root- > right);}

Complexity analysis:

Time complexity: O (N2), where n is the number of nodes in the binary tree.

In the worst case, the binary tree is full binary tree, and the main function isBalanced (root) needs to traverse all the nodes in the binary tree, and the time complexity is O (n). The function TreeDepth (root) for calculating the maximum height of each subtree is called repeatedly. Except for the root node, all other nodes are traversed twice with a complexity of O [2 (NMUI 1)], so the time complexity is Nim2 (NMel 1) ≈ N2.

Space complexity: O (n), where n is the number of nodes in the binary tree. The space complexity mainly depends on the number of layers of recursive calls, which will not exceed n.

Bottom-up recursion (optimal solution)

Method one is recursive from top to bottom, similar to preorder traversal, which first determines whether the current tree is balanced, and then determines whether the left and right subtrees of the current tree are balanced, so for the same node, the function TreeDepth will be called repeatedly, and the height of many secondary subtrees will be repeatedly calculated, resulting in high time complexity.

If you use a bottom-up approach, the function TreeDepth is called only once for each node. Because after reaching the bottom of the left subtree, each corresponding left subtree is placed in the recursive scheduling, and only the new length of the right subtree needs to be obtained each time.

Bottom-up recursion is similar to post-order traversal, for the current traversal node, first recursively judge whether the left and right subtrees are balanced, and then judge whether the subtrees with the current node as the root are balanced.

If there is only one imbalance in the left / right subtree of the current tree, the whole tree is unbalanced and returns-1 (indicating imbalance).

If the current tree is balanced, its height is returned, otherwise-1 (indicating imbalance) is returned.

What do you need to focus on writing recursive algorithms?

The termination condition of the whole recursion: when should the recursion end? When the root node of the subtree is empty, the empty tree is also a balanced binary tree.

What should be done by this level of recursion? -determine whether the left subtree, the right subtree, and the current tree of the current tree are balanced.

Return value: what is the return value that should be returned to the higher level? -if the current tree is balanced, its height is returned, and if unbalanced,-1 is returned.

Recursive algorithm flow:

Each level of recursion, in our eyes, the current tree is like this, only root, left, right three nodes.

When it comes to the leaf node, the root of the current tree root node is empty, which means it is balanced, then the height 0 is returned.

The current root node root is not empty. Calculate the heights of the left and right subtrees left and right, and determine:

If "left subtree left height is-1", or "right subtree right height is-1", or "left and right subtree height difference > 1", the whole tree is unbalanced and directly returns-1 (indicating imbalance).

If the above three cases are not satisfied, the current tree is balanced and the height of the current tree is returned, that is, max (left, right) + 1.

Add: the function that calculates the absolute value: int abs (int n); header file or.

Recursive process demonstration: bottom-up recursion is similar to post-order traversal

/ * Definition for a binary tree node. * struct TreeNode {* int val; * struct TreeNode * left; * struct TreeNode * right; *} * / / calculate the height of the current tree and determine whether the current tree is a balanced binary tree int _ isBalanced (struct TreeNode* root) {/ / first determine whether the left / right subtrees of the current tree are balanced / / if there is only one imbalance in the left / right subtree of the current tree, the whole tree is unbalanced and returns-1 (indicates imbalance) / / if both the left and right subtrees of the current tree are balanced Continue to determine whether the current tree is balanced / / 1. When it comes to the leaf node, if the root node of the current tree is empty, which means it is balanced, the height 0 if (root = = NULL) {return 0;} / / 2 is returned. The current root node is not empty / / calculate the height of the left and right subtrees int leftTreeDepth = _ isBalanced (root- > left); int rightTreeDepth = _ isBalanced (root- > right); / / three cases of imbalance: the height of the left subtree is-1, the height of the right subtree is-1, and the height difference between the left and right subtrees is > 1 if (leftTreeDepth = =-1 | | rightTreeDepth = =-1 | | abs (leftTreeDepth-rightTreeDepth) > 1) {return-1) } / / if the above three cases are not satisfied, the current tree is balanced and the height of the current tree is returned return leftTreeDepth > rightTreeDepth? LeftTreeDepth + 1: rightTreeDepth + 1;} bool isBalanced (struct TreeNode* root) {/ / Recursive traversal: / / as long as there is a subtree with a height of-1, the whole tree is unbalanced, and false / / all subtrees are not equal to-1 in height, indicating that the whole tree is balanced and true return _ isBalanced (root)! =-1;}

Complexity analysis:

1. Time complexity: O (n), where n is the number of nodes in the binary tree.

In the worst case, when the binary tree is a full binary tree, it needs to traverse all the nodes in the complete binary tree, bottom-up method, so each node will only be traversed once, so the time complexity is O (n).

two。 Space complexity: O (n), where n is the number of nodes in the binary tree. The space complexity depends on the number of layers of recursive calls. The depth of a binary tree with n nodes is the highest when it is a unilateral tree, which is n.

This is the end of the introduction on "how to solve the problem of balanced binary tree in C language". Thank you for your reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

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.