This is the 7th day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

preface

  • Updated todayOn the seventh dayAnd finally met the requirements of the first level of the article,Writing the article took a lot of time(Du itself is very slow to write, plus I have certain requirements for the quality of the article,So just...), but the thought of itMore wen reward, I will againpower!!! Ha, ha, ha.
  • Doodle still canEnsure the quality of articlesI don’t send some hydrology just because I want to participate in the eventThis is a waste of readers' time, but also a waste of small du's timeIn the end the article is worthless which I don’t want to see.
  • Hopefully, readers will find it rewarding.
  • Today, back to the update binary tree series, the article will not be long, please read patiently.
  • Note: this du is an algorithm dregs, (when the interview let write a non-recursive sequence traversal did not write out, alas), so, I write the purpose of the article isFor those of you who want to learn the algorithm, but are still confused after reading the algorithm titleLarge,God please go around!

purpose

  • The purpose of this article: du with the reader to do binary tree related topics, and then du summed up their own perception.
  • Before we have taken the binary tree of three traversal calculation method have learned (including recursion and non-recursion), not please slide to the bottom of the article, small du at the bottom of the link oh!

The body of the

  • First of all, let’s look at the problem

  • Let’s find the KTH node of a binary search tree. Toot is still putting a graph

  • There’s a term for binary tree, binary search tree, so what is a binary search tree?
  • Small duonTime:Binary search tree, xiao Du’s understanding is that the left child of a node is smaller than it, and its right child is larger than it. Therefore, we can know that the binary search tree has a property:Every left subtree of a node has val less than or equal to it, and every right subtree has val greater than or equal to it.

  • Once the concept is clear, analyze the topic

    • First of all, given the constraints of the problem,Root is not an empty tree(because itK limitThe condition tells us it must find an element.
    • We want to find the KTH largest element, so we have to go through the binary tree, right? How to traverse this is a problem. Think about it: to iterate and find the KTH element, do we first need to find an increasing or decreasing order? Oh, aha! We’re looking for an order that either increases or decreases.
    • Now it’s time to think about which way should we traverse? Before the order? In the order? After the order? Think about the order in which they are traversed, and the properties of binary trees, and the fact that we’re looking for an increasing or decreasing order.
    • After the analysis,We chose middle order traversalThis is an increasing order. (There’s another way! I don’t know what to call it, just call it false middle order traversal, hahaha)

  • Just look at the code

  • The recursive version of the

var kthLargest = function(root, k) {
    let res=[];
    const Kmax = (root01)=>{
        if(root01 == null) return;
        Kmax(root01.left);
        res.push(root01.val);
        Kmax(root01.right)
    }
    Kmax(root);
    let length = res.length;
    return res [length-k];
};
Copy the code

  • The iterative version of
var kthLargest = function(root, k) {
    let res=[];
    let stack = [];
    while(root || stack.length ){
        while(root){
            stack.push(root);
            root = root.left;
        }
        let node = stack.pop();
        res.push(node.val);
        root = node.right;
    }
    let length = res.length;
    return res [length-k];
};
Copy the code

Another way to do it

  • So the idea is still the same, but we’re looking for an ordered order, and we’re looking for a decreasing order.

  • The recursive version of the

var kthLargest = function(root, k) {
    let res=[];
    const Kmax = (root01)=>{
        if(root01 == null) return;
        Kmax(root01.right);
        res.push(root01.val);
        Kmax(root01.left)
    }
    Kmax(root);
    return res[k-1];
};
Copy the code

  • The iterative version of
 var kthLargest = function(root, k) {
    let res=[];
    let stack = [];
    while(root || stack.length ){
        if(res.length == k) return res[k-1];
        while(root){
            stack.push(root);
            root = root.right;
        }
        let node = stack.pop()
        res.push(node.val);
        root = node.left;
    }
    return res[k-1];
};
Copy the code

  • La la la, small du finished speaking, feeling stillThe binary tree problem is inseparable from three traversal methodsSo we’re going to do binomial tree problems. First of all, we’re going tomasterThree basic traversal sequences.

Slip slip slip...

At the end

  • I hope all of you who are learning algorithms canHang in there, come on!
  • If you have any questions, welcome to leave a message below, small du see will be the first time to reply.
  • Creation is not easy, feel good, welcome to support!
  • Think more, do more, try moreIf not, look at the code and use the code to understand.

The attachment

  • Binary tree traversal: juejin.cn/post/702968…

  • Sequential traversal in a binary tree

    • Recursive version: juejin.cn/post/702748…
    • Iteration: juejin.cn/post/702774…

  • Binary tree post order traversal: juejin.cn/post/702911…

  • Binary tree traversal (5 – final):juejin.cn/post/703058…