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

This article mainly explains "how to solve the next node of the binary tree by C++". The content of the explanation in the article is simple and clear, and it is easy to learn and understand. let's study and learn "how to solve the next node of the binary tree by C++".

Topic description

Given one of the nodes in a binary tree, find the next node in the traversal order and return. Note that the node in the tree contains not only the left and right child nodes, but also the next pointer to the parent node. The following picture shows a binary tree with nine nodes. The pointer from the parent node to the child node in the tree is represented by a solid line, and the pointer from the child node to the parent node is represented by a dashed line

Example:

Input: {8, 6, 10, 5, 7, 9, 11}, 8

Return: 9

Analysis: the root node of the subtree passed in this assembly is actually the whole tree. The middle order traverses {5grad, 6magh, 7je, 8pm, 9pm, 10pm, 11}, and the next node of root node 8 is 9, which should be returned. In the background, only the next node of the subtree is printed, so only 9 will be printed. As shown in the following figure, there are pointers to the left and right children and pointers to the parent node, but the next picture is not drawn.

Data range: the number of nodes satisfies 1 ≤ n ≤ 50, and the values on nodes meet 1 ≤ val ≤ 100

Requirements: space complexity O (1), time complexity O (n)

Example:

Enter:

{8,6,10,5,7,9,11}, 8

Return value:

nine

Problem-solving ideas

This topic examines the use of data structure trees. Two methods:

1) brute force cracking. Get the root node through the next pointer, sort it in the middle order, store it with vector in the sorting process, and then output it directly according to the location.

2) combined with the properties of middle order sorting. If a node has a right subtree, the leftmost child of the right subtree is its next node; if there is no right subtree, its first right father is its next node.

Test code 1) brute force cracking / * struct TreeLinkNode {int val; struct TreeLinkNode* left; struct TreeLinkNode* right; struct TreeLinkNode* next; TreeLinkNode (int x): val (x), left (NULL), right (NULL), next (NULL) {}}; * / class Solution {public: TreeLinkNode* GetNext (TreeLinkNode* pNode) {if (! pNode) return NULL / / determine the root node TreeLinkNode* root=pNode; while (root- > next) {root=root- > next;} / / medium order sort vector v; inorder (root,v); for (int iS0 alternative iRightPersonality v);}}; 2) combine the medium order sorting properties / * struct TreeLinkNode {int val; struct TreeLinkNode* left; struct TreeLinkNode* right Struct TreeLinkNode* next; TreeLinkNode (int x): val (x), left (NULL), right (NULL), next (NULL) {}}; * / class Solution {public: TreeLinkNode* GetNext (TreeLinkNode* pNode) {if (! pNode) return NULL; / / determine whether there is a right subtree if (pNode- > right) {TreeLinkNode* target=pNode- > right / / take the leftmost child while (target- > left) {target=target- > left;} return target;} / / there is no right subtree, and find the first right father while (pNode- > next) {if (pNode- > next- > left==pNode) return pNode- > next PNode=pNode- > next;} return NULL;}}; thank you for reading. The above is the content of "how to solve the next node of the binary tree on C++". After the study of this article, I believe you have a deeper understanding of how to solve the problem of how to solve the next node of the binary tree on C++, 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.