This is the 23rd day of my participation in the August More Text Challenge.More challenges in August

Tree 🌲

traverse

Constructing binary tree by traversing sequence: + middle; After +; Sequence +

The first sequence traversal

Void PreOrder(BiTree T){if(T! = NULL){ visit(T); // Access the root node PreOrder(T->lchild); PreOrder(T->rchild); // Recursively traverse the right subtree}}Copy the code

In the sequence traversal

Void InOrder(BiTree T){if(T! = NULL){ InOrder(T->lchild); Visit (T); visit(T); // access the root node InOrder(T->rchild); // Recursively traverse the right subtree}}Copy the code

After the sequence traversal

Void PostOrder(BiTree T){if(T! = NULL){ PostOrder(T->lchild); PostOrder(T->rchild); // recursively traverse the right subtree visit(T); // Access the root node}}Copy the code
  • I’m sure you’re familiar with tree traversal, but let’s do tree arithmetic
  • How do we apply tree traversal
  • See the topic!
  • Given a binary search tree, find the KTH largest node.
  • Enter: root = [3,1,4,null,2], k = 1
3 / \ 1 4\2 Output: 4Copy the code
  • The first thing we should think about when we get this problem is, the dumbest way to do it is
  • Maintain an extra space to store all the nodes in the tree
  • Turn the problem into a sorted array, looking for the KTH largest node
  • But let’s think about if we can take advantage of the tree traversal property, the middle order traversal of a binary search tree is sort from largest to smallest
  • So the breakthrough of our problem is the middle order traversal of binary search tree

  • In the code, we can see that we maintain a counter like principle globally
  • We’re counting in terms of c, but the point ismake(TreeNode node)function
  • make(TreeNode node)The function simply follows the tree’s middle-order traversal code template
  • Right-center-left, after each judgment on the right node, the counter (c) is subtracted by one
  • Then we should pay attention to the exit points and special judgment conditions of the auxiliary function

conclusion

  1. Although this problem is easy, but we make it is not the purpose, but to think about the hidden logic behind the problem
  2. As you can see from this simple and simple problem, the three tree traversal methods can be applied to many problems
  3. So often very small and very important links, but we think that usually do not use