This series is mainly to record the process of my brush questions. The key is to solve each type of problem step by step, according to this order of basic every problem can be done. Rather than a solution to a problem, so it is suitable for people who plan to brush a lot of reference. Binomial tree – related brush problem order is a reference code catalog.

LeetCode_ Binary Tree Brush Problem Note 4(Java)

LeetCode_ Binary Tree Brush problem Note 3(Java)

LeetCode_ Binary Tree Brush Problem Notes 2(Java)

LeetCode_ Binary Tree Brush problem Notes 1(Java)

The next few questions are still about binary search trees.

Binary search tree

701. Insert operations in binary search trees

Difficulty Medium 159

Inserts the value into the binary search tree (BST) given the root node and the value in the tree to be inserted. Returns the root node of the inserted binary search tree. The input data guarantees that the new value is different from any node in the original binary search tree.

Note that there may be several effective ways to insert, as long as the tree remains a binary search tree after insertion. You can return any valid result.

Example 1:

Input: root = [4,2,7,1,3], val = 5 output: [4,2,7,1,3,5]Copy the code

Example 2:

Input: root = [40,20,60,10,30,50,70], val = 25 output: [25] 40,20,60,10,30,50,70, null, null,Copy the code

Example 3:

Input: root = [4,2,7,1,3, null, null, null, null, null, null], val = 5 output:,2,7,1,3,5 [4]Copy the code

Tip:

  • The number of nodes in a given tree is between0 和 10 ^ 4between
  • Each node has a unique integer value ranging from0 到 10 ^ 8
  • -10^8 <= val <= 10^8
  • The new value is different from any node in the original binary search tree

Train of thought

The new value is different from any node in the original binary search tree. In this way, without changing the original tree structure, you only need to put the value less than the current node to the left, and the value greater than the current node to the right, and only when the current node is empty, the node can be inserted.

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
      	// You can return to the new node
        if(root==null)return new TreeNode(val);
				// Insert to the left
        if(root.val>val){
            TreeNode left = insertIntoBST(root.left,val);
            if(left! =null) root.left=left;
        }
      	// Insert to the right
        if(root.val<val){
            TreeNode right=insertIntoBST(root.right,val);
            if(right! =null) root.right=right;
        }

        returnroot; }}Copy the code

450. Delete nodes in the binary search tree

Difficulty Medium 395

Given the root node of a binary search tree root and a value of key, delete the nodes corresponding to key in the binary search tree and ensure that the properties of the binary search tree remain unchanged. Returns a reference to the root node of the binary search tree (which may be updated).

In general, node deletion can be divided into two steps:

  1. First find the node to delete;
  2. If found, delete it.

Note: The algorithm time complexity is O(h), h is the height of the tree.

Example:

Root = [5,3,6,2,4,null,7] key = 3 5 / \ 3 6 / \ 2 4 7 5 / \ 3 6 / \ 2 4 7 A correct answer is [5,4,6,2,null,null,7], as shown below. 5 / \ 4 6 / \ 27 Another correct answer is [5,2,6,null,4,null,7]. 5 / \ 2 6\4 7Copy the code

Train of thought

The big idea is not hard. Lots of details.

  • Find the target node (recursively, pre-traversal)
  • Use the front node of the current node as the new root node (using the back node is also possible)
  • Deleting a Target Node

Details in the source code note:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null)return null;
        // Find the node to delete
        if (root.val == key) {
            // The target node has left and right child nodes
            if(root.left! =null&&root.right! =null) {// Find the front connector of the destination node
                if(root.left.right! =null){
                    TreeNode node =root.left.right;
                    TreeNode preNode =root.left;
                    // Keep looking for the right node
                    while(node.right! =null){
                        preNode=node;
                        node=node.right;
                    }
                    // The left node of the front node is not empty,
                    if(node.left! =null){
                        preNode.right=node.left;
                        node.left =root.left;
                        node.right = root.right;
                        return  node;
                    }else{
                        preNode.right =  null;
                        node.left =root.left;
                        node.right = root.right;
                        returnnode; }}else{
                    // If the front node is the left node of the node, use the left node as the root node
                    root.left.right=root.right;
                    TreeNode newNode =root.left;
                    root=null;
                    returnnewNode; }}// You need to return a root node that has been removed and rebuilt as BST
            if(root.left==null&&root.right==null) {// The target node is a leaf node
                return  root=null;
            }
            // Return a non-null child node
            returnroot.left! =null? root.left:root.right; }if (root.val > key) {
            root.left= deleteNode(root.left, key);
        }
        if (root.val < key) {
            root.right = deleteNode(root.right, key);
        }
        returnroot; }}Copy the code

669. Trim the binary search tree

Difficulty medium 351

You are given the root node of the binary search tree, root, with a minimum boundary low and a maximum boundary high. By pruning the binary search tree, the values of all nodes are in [low, high]. Pruning the tree should not change the relative structure of the elements that remain in the tree (that is, if they are not removed, the original parent and child relationships should remain). It can be argued that there is a single answer.

So the result should return the new root node of the pruned binary search tree. Note that the root node may change depending on the given boundary.

Example 1:

Root = [1,0,2], low = 1, high = 2Copy the code

Example 2:

Input: root = [3,0,4, NULL,2, NULL, NULL,1], low = 1, high = 3Copy the code

Example 3:

Input: root = [1], low = 1, high = 2Copy the code

Example 4:

Input: root = [1,null,2], low = 1, high = 3Copy the code

Example 5:

Input: root = [1, NULL,2], low = 2, high = 4Copy the code

Tip:

  • The number of nodes in the tree is in the range[1, 104] 内
  • 0 <= Node.val <= 104
  • Each node in the tree has a unique value
  • The problem data guarantees that the input is a valid binary search tree
  • 0 <= low <= high <= 104

Train of thought

Again, I’m going to recursively go from top to bottom. If it does not match [L,R], delete it.

Note that one node has a value less than L, but its right node may be approximately L.

Similarly, some node has a value greater than R, but its left node may be less than or equal to R. Such nodes cannot all be deleted

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root==null) return null;
        if(root.val<low){
          	// The right node of this node may be >=low
            return trimBST(root.right,low,high);
        }
        if(root.val>high){
          	// The left child of this node pits you <=heig
            return trimBST(root.left,low,high);
        }
		
        root.left = trimBST(root.left,low,high);
        root.right = trimBST(root.right,low,high);
        returnroot; }}Copy the code

108. Convert an ordered array to a binary search tree

Difficulty simple 701

Given an array of integers, numS, whose elements are sorted in ascending order, convert it into a highly balanced binary search tree.

A highly balanced binary tree is one that satisfies the requirement that the absolute value of the height difference between the left and right subtrees of each node is no more than 1.

Example 1:

Input: nums = [-, 10-3,0,5,9] output: [0, 3, 9, 10, null, 5] : [0, 10, 5, null, 3, null, 9] also will be deemed to be the correct answer:Copy the code

Example 2:

Input: nums = [1,3] output: [3,1] explanation: [1,3] and [3,1] are both highly balanced binary search trees.Copy the code

Tip:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 按 Strictly increasingorder

Train of thought

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
            return  sortedArrayToBST(0,nums.length-1,nums);
    }
    //[start,end]
    private  TreeNode sortedArrayToBST(int start,int end,int[] nums){
        if(start>end) return null;
        // In the middle note +start
        int mid = start+((end-start)>>1);
        TreeNode root=new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(start,mid-1,nums);
        root.right = sortedArrayToBST(mid+1,end,nums);

        returnroot; }}Copy the code

538. Convert a binary search tree to a summation tree

The difficulty is medium 478

Convert the root node of the binary search Tree to the Greater Sum Tree. Make the new value of node of each node equal to the Sum of the values Greater than or equal to node.val in the original Tree.

As a reminder, binary search trees satisfy the following constraints:

  • The left subtree of a node contains only nodes whose keys are smaller than the node’s keys.
  • The right subtree of a node contains only nodes whose keys are greater than the node’s keys.
  • The left and right subtrees must also be binary search trees.

** Note: ** in this case and 1038: leetcode-cn.com/problems/bi… The same

Example 1:

Input: [4,1,6,0,2,5,7, null, null, null, 3, null, null, null, 8] output: [30,36,21,36,35,26,15, null, null, null, 33, null, null, null, 8]Copy the code

Example 2:

Input: root = [0, NULL,1]Copy the code

Example 3:

Input: root = [1,0,2]Copy the code

Example 4:

Input: root = [3,2,4,1]Copy the code

Tip:

  • The number of nodes in the tree is between0 和 104In between.
  • Each node has a value between- 104. 和 104In between.
  • All the values in the tree are different.
  • The given tree is a binary search tree.

Train of thought

This one looks kind of spooky. But it’s easy to figure out what a summation tree is, and how to calculate the value of a summation tree.

As shown below, the sum can be added in the order of right -> middle -> left:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
  	// Record the value of the previous node
    int preValue =0;
    public TreeNode convertBST(TreeNode root) {

        // What is an accumulation tree?
        // How is the value of the summation tree calculated?
        if(root==null) return null;
        convertBST(root.right);
        root.val+=preValue;
        preValue=root.val;
        convertBST(root.left);

        returnroot; }}Copy the code

Restore binary search tree

Difficulty Difficulty 415

Given the root node of a binary search tree, root, two nodes in the tree were swapped by mistake. Please restore the tree without changing its structure.

** Advancements: ** Solutions are easy to implement using O(n) space complexity. Can you come up with a solution that only uses constant space?

Example 1:

Input: root = [1,3, NULL, NULL,2] Output: [3,1, NULL,null,2] Swap 1 and 3 to make the binary search tree valid.Copy the code

Example 2:

Input: root = [3,1,4, NULL, NULL,2] Output: [2,1,4, NULL, NULL,3] Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swap 2 and 3 to make the binary search tree valid.Copy the code

Tip:

  • The number of nodes in the tree is in the range[2, 1000] 内
  • -231 <= Node.val <= 231 - 1

Train of thought

First of all, we need to know that the order traversal in a binary search tree is going to be an ascending order.

If the tree is defective, then there are inversions in the ascending order. And they say there’s only one pair of inversions.

So the values need to find the reverse pair, and then swap the values:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {

    // The node of the last intermediate traversal
    private TreeNode prev;
    // The first error node
    private TreeNode first;
    // The second error node
    private TreeNode second;
    public void recoverTree(TreeNode root) {
        findWrongNodes(root);  
        // Swap the values of the two error nodes
        int temp=second.val;
        second.val=first.val;
         first.val=temp;

    }

    private void findWrongNodes(TreeNode root){
        if(root==null) return;
      	// Notice the middle order traversal
        findWrongNodes(root.left);
        if(prev! =null&&prev.val>root.val){
            // inversions occur
            // The second error node is the smaller node in the last inversion pair
            second=root;
            // The first error node is the larger node in the first inversion pair
            if(first! =null) return; first=prev; } prev=root; findWrongNodes(root.right); }}Copy the code

333. Maximum BST subtree

Difficulty medium 81

Given a binary tree, find the largest binary search tree (BST) subtree and return the size of that subtree. The largest refers to the node with the largest number of subtrees.

** All nodes in the binary search tree (BST) ** have the following properties:

  • The value of the left subtree is less than the value of its parent (root) node.
  • The value of the right subtree is greater than that of its parent (root) node.

Note:

  • A subtree must contain all its descendants.

Advanced:

  • Can you think of a solution in order n time?

Example 1:

Input: root = [10,5,15,1,8,null,7] output: 3 explanation: the largest BST subtree in this example is the one highlighted. The return value is the size of the subtree, which is 3.Copy the code

Example 2:

Input: root = [4,2,7,2,3,5, null, 2, null, null, null, null, null, 1] output: 2Copy the code

Tip:

  • The number of nodes in the tree ranges from[0, 104]
  • -104 <= Node.val <= 104

Train of thought

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
    public int largestBSTSubtree(TreeNode root) {
        return (root==null)?0:getInfo(root).size;
    }
   // Get the maximum BST subtree of the binary tree where the current node is the root node
    private Info getInfo(TreeNode node){
        if(node==null)return null;
        // Maximum BST information for the left subtree
        Info li=getInfo(node.left);
        // Maximum BST information for the right subtree
        Info ri=getInfo(node.right);

        int leftBstSize=-1,rightBstSize=-1,min=node.val,max=node.val;

      // The left subtree does not have BST, or the left subtree is BST
        if(li==null){
            leftBstSize=0;
        }else if(li.root==node.left&&node.val>li.max){
            leftBstSize=li.size;
            min=li.min;
        }
			// The right subtree has no BST, or the right subtree is BST
        if(ri==null){
            rightBstSize=0;
        }else if(ri.root==node.right&&node.val<ri.min){
            rightBstSize=ri.size;
            max=ri.max;
        }
        // The binary tree with node as the root is BST
        if(leftBstSize>=0&&rightBstSize>=0) {return new Info(node,1+leftBstSize+rightBstSize,min,max);
        }
    
        // A binary tree with node as the root is not a BST
        if(li! =null&&ri! =null)return(li.size>ri.size)? li:ri;return(li! =null)? li:ri; }private static class Info{

       public TreeNode root;
       public int size;
       public int min;
       public int max;

    public Info(TreeNode root,int size,int min,int max){
        this.root= root;
        this.size=size;
        this.min=min;
        this.max=max; }}}Copy the code

Minimum common area

235. The nearest common ancestor of binary search trees

The difficulty is simple

Given a binary search tree, find the most recent common ancestor of two specified nodes in the tree.

The definition of the nearest common ancestor in Baidu encyclopedia is: “For the two nodes P and Q with root tree T, the nearest common ancestor is expressed as a node X, satisfying that X is the ancestor of P and Q and x is as deep as possible (a node can also be its own ancestor).

For example, given the following binary search tree: root = [6,2,8,0,4,7,9, null, null, 3, 5)

Example 1:

Input: root = [6,2,8,0,4,7,9, null, null, 3, 5), p = 2, q = 8 output: 6: node 2 and 8 of recent common ancestor is 6.Copy the code

Example 2:

Input: root = [6,2,8,0,4,7,9, null, null, 3, 5), p = 2, q = 4 output: 2: recent common ancestor node 2, and 4 is 2, because recent common ancestor nodes can be according to the definition for the node itself.Copy the code

Description:

  • All nodes have unique values.
  • P and Q are different nodes and exist in the given binary search tree.

Train of thought

First of all, we need to know the characteristics of binary tree search tree. The left subtree node of the current node is smaller than it, and the right subtree node is larger than it. According to this rule, the recursion can be solved:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return root;

        If the current value is greater than p and q, the common ancestor must be in the left subtree of the current node
        if (root.val > p.val && root.val > q.val) {
            //left
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            if(left ! =null) return left;

        }
        If the current value is less than p and q, the common ancestor must be in the right subtree of the current node
        if (root.val < p.val && root.val < q.val) {
            //right
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if(right ! =null) return right;
        }
        // if p is greater than root and q is less than root, one is to the left of root and one is to the right of root. So root is their common ancestor
        returnroot; }}Copy the code

236. The most recent common ancestor of binary trees

The difficulty is medium 947

Given a binary tree, find the nearest common ancestor of the two specified nodes in the tree.

The definition of the nearest common ancestor in Baidu Encyclopedia is as follows: “For two nodes P and Q with root tree T, the nearest common ancestor is expressed as a node X, which satisfies that X is the ancestor of P and Q and the depth of X is as large as possible (a node can also be its own ancestor).

Example 1:

Input: root = [3,5,1,6,2,0,8, null, null, 7, 4], p = 5, output q = 1:3: node 5 and 1 recent common ancestor node 3.Copy the code

Example 2:

Input: root = [3,5,1,6,2,0,8, null, null, 7, 4], p = 5, q = 4 output: 5: node 5 nodes and four recent common ancestor is 5. Because by definition the nearest common ancestor node can be the node itself.Copy the code

Example 3:

Input: root = [1,2], P = 1, q = 2 Output: 1Copy the code

Tip:

  • The number of nodes in the tree is in the range[2, 105]Inside.
  • -109 <= Node.val <= 109
  • allNode.val Each other is not the same 。
  • p ! = q
  • p 和 qAll exist in a given binary tree.

Train of thought

In this case, to find the common ancestor, you have to go from the bottom up. The first thought must be depth first, because it is to find a common ancestor, the root node must be the last traversal, so it is more appropriate to use post-order traversal at this time.

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // The recursive exit condition is returned when p is found or q is found, or there is no node.
        if(root==p||root==q||root==null) return root;

        / / after order
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        // If p and Q are on the left and the other on the right, root must be their nearest common ancestor
        if(right! =null&&left! =null) return root;
        
        return(left! =null)? left:right; }}Copy the code

1257. Minimum common area

The difficulty of medium

You are given a list of regions. The first region of each list contains all the other regions in the list.

Naturally, if region X contains region Y, then region X is larger than region Y.

Given two regions region1 and Region2, find the smallest region containing both regions.

If R1 in the range list contains R2 and R3, the data guarantees that R2 does not contain R3.

The data also ensures that the minimum common area exists.

Example 1:

Input:  regions = [["Earth","North America","South America"], ["North America","United States","Canada"], ["United States","New York","Boston"], ["Canada","Ontario","Quebec"], ["South America","Brazil"]], region1 = "Quebec", Region2 = "New York" output: "North America"Copy the code

Tip:

  • 2 <= regions.length <= 10^4
  • region1 ! = region2
  • All strings contain only English letters and Spaces and can contain a maximum of 20 letters

Train of thought

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

class Solution {
    private RegionTreeNode root;
    private Map<String,RegionTreeNode> m_cache = new HashMap<>();

    /** * area tree node class */
    private static class RegionTreeNode {
        String key;/ / key
        RegionTreeNode parent;/ / the parent node

        RegionTreeNode(String key) {
            this(key,null);
        }

        RegionTreeNode(String key, RegionTreeNode parent) {
            this.key = key;
            this.parent = parent; }}/** * Build tree structure *@param regions
     */
    private void buildRegionTree(List<List<String>> regions){
        for (List<String> list : regions){
            // Get the key of the parent node
            String parentKey = list.get(0);
            if (root == null) {
                root = new RegionTreeNode(parentKey);
                m_cache.put(parentKey,root);
            }
            // The first node is the parent
            RegionTreeNode parentNode = m_cache.get(parentKey);
            for (int i = 1; i<list.size(); i++){ String key = list.get(i); RegionTreeNode node =new RegionTreeNode(key);
                m_cache.put(key,node);// add cachenode.parent = parentNode; }}}public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
        buildRegionTree(regions);
        RegionTreeNode node1 = m_cache.get(region1);
        RegionTreeNode node2 = m_cache.get(region2);
        Set<String> set = new HashSet<>();
        while(node1 ! =null){
            set.add(node1.key);
            node1 = node1.parent;
        }
        while(node2 ! =null) {if (set.contains(node2.key)){
                return node2.key;
            }
            node2 = node2.parent;
        }
        return null; }}Copy the code