[brother hero July training] day 20: search Binary Tree

Series articles

【 Brother hero training in July 】 The first 01 God : Array

【 Brother hero training in July 】 The first 02 God : character string

【 Brother hero training in July 】 The first 03 God : Sort

【 Brother hero training in July 】 The first 04 God : greedy

【 Brother hero training in July 】 The first 05 God : Double pointer

【 Brother hero training in July 】 The first 06 God : The sliding window

【 Brother hero training in July 】 The first 07 God : Hashtable

【 Brother hero training in July 】 The first 08 God : The prefix and

【 Brother hero training in July 】 The first 09 God : Two points search

【 Brother hero training in July 】 The first 10 God : An operation

【 Brother hero training in July 】 The first 11 God ： matrix

【 Brother hero training in July 】 The first 12 God ： Linked list

【 Brother hero training in July 】 The first 13 God ： Double linked list

【 Brother hero training in July 】 The first 14 God ： Stack

【 Brother hero training in July 】 The first 15 God ： Depth-first search

【 Brother hero training in July 】 The first 16 God ： queue

【 Brother hero training in July 】 The first 17 God ： Breadth first search

【 Brother hero training in July 】 The first 18 God ： Trees

【 Brother hero training in July 】 The first 19 God ： Binary tree

【 Brother hero training in July 】 The first 20 God ： Search binary trees

---

One 、938. The range of binary search tree and

938. The range of binary search tree and

leetcode938 java

class Solution {
    
    public int rangeSumBST(TreeNode root, int low, int high) {
    
        
        if(root==null){
    
            return 0;
        }
        int sum=0;
        if(root.val<=high && root.val>=low){
    
            sum+=root.val;
        } 
        return sum+rangeSumBST(root.left,low,high)+rangeSumBST(root.right,low,high) ;

    }
}

Two 、 The finger of the sword Offer II 054. Sum of all values greater than or equal to nodes

The finger of the sword Offer II 054. Sum of all values greater than or equal to nodes

leetcode The finger of the sword Offer II 054 java

class Solution {
    
    public TreeNode convertBST(TreeNode root) {
    
        int sum = 0;
        TreeNode node = root;

        while (node != null) {
    
            if (node.right == null) {
    
                sum += node.val;
                node.val = sum;
                node = node.left;
            } else {
    
                TreeNode succ = getSuccessor(node);
                if (succ.left == null) {
    
                    succ.left = node;
                    node = node.right;
                } else {
    
                    succ.left = null;
                    sum += node.val;
                    node.val = sum;
                    node = node.left;
                }
            }
        }

        return root;
    }

    public TreeNode getSuccessor(TreeNode node) {
    
        TreeNode succ = node.right;
        while (succ.left != null && succ.left != node) {
    
            succ = succ.left;
        }
        return succ;
    }
}

---

summary