Li Kou Jianzhi offer -- binary tree chapter

Preface

Hello everyone ！ Long time no see. I'm blue and white porcelain , Did you brush the questions today ？ List of articles , From easy to difficult , Step by step , This issue is a combination of Niuke 101 And the sword finger offer The above binary tree series OJ Interview questions , Learning together , Progress together . If the solution is helpful to you , A little bit of praise to support , If there is something wrong , Welcome to correct
The series recommends :：
1. Basic operation of binary tree
2. First, middle and last traversal of binary tree （ Recursion and iteration ）
3.【Java data structure 】 Binary tree, binary tree advanced —— Dachang classic OJ Interview questions —— Brush notes + How to do it

---

Collection of brush questions of binary tree

Print binary tree

---

The finger of the sword Offer 32 - I. Print binary tree from top to bottom

OJ link ： Print binary tree from top to bottom

Title Description ：

Their thinking ：

First read the meaning of the question , This problem is a Sequence traversal binary tree , But it needs to be returned to an array .

Specific steps ：

1. To borrow The order sheet Used to store the value of each node of the binary tree
2. To borrow Secondary queue To complete the sequence traversal operation of binary tree
3. Traverse The order sheet , Put the... Of each node in the order table It's worth going back to Array

The code is as follows ：

class Solution {
    public int[] levelOrder(TreeNode root) {
        // Sequence traversal   A line   A sequence table 
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        //  If the header node is empty   Return to one   New array 
        if(root == null) return new int[0];
        //  If it's not empty   Put the element   Put in   In line 
        queue.add(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            list.add(cur.val);
            if(cur.left != null) {
                queue.add(cur.left);
            }
            if(cur.right != null) {
                queue.add(cur.right);
            }
        }
        int[] ret = new int[list.size()];
        for(int i = 0;i < list.size();i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }
}

---

The finger of the sword Offer 32 - II. Print binary tree from top to bottom II

OJ link ： Print binary tree from top to bottom II

Title Description ：

Their thinking ： This question is consistent with the previous one , Only this problem returns a two-dimensional array , In a nutshell , It's on the original one-dimensional array , Another layer of array is nested , This problem needs to pay attention to several details , as follows ：

1. Sequence traversal Indispensable auxiliary queue
2. Return a two-dimensional array , We need a Two dimensional array receiving Return value
3. Need to use A one-dimensional array first receives the value of each layer of nodes , Need here Be careful , Receive the value of each layer node , Need to be put into the loop , Ensure the number of values of each layer
4. Specifically , Look at the code , Detailed notes

The code is as follows ：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //  Sequence traversal   Indispensable   auxiliary   queue 
        Queue<TreeNode> queue = new LinkedList<>();
        //  Returns a binary array 
        List<List<Integer>> ret = new ArrayList<>();
        //  Same , First determine whether the end node is empty 
        if(root == null) return ret;
        //  Not empty  root  Such as queue 
        queue.add(root);
        //  The loop condition 
        while(!queue.isEmpty()) {
            //  Because what we return is a two-dimensional array , Here we first use a one-dimensional array to receive the value of each node 
            List<Integer> list = new ArrayList<>();
            //  Here we want to guarantee , The value of each one-dimensional array , Here we need a layer of circulation 
            for(int i = queue.size();i > 0;i--) {
            //  eject   queue   Head   Elements , use  cur  receive 
            TreeNode cur =  queue.poll();
            list.add(cur.val);
            if(cur.left != null) {
                queue.add(cur.left);
            }
            if(cur.right != null) {
                queue.add(cur.right);
            }   
          }
          //  Cycle time , Put it once 
            ret.add(list);
        }
        //  Finally, return a two-dimensional array 
        return ret;
    }
}

---

The finger of the sword Offer 32 - III. Print binary tree from top to bottom III

OJ link ： Print binary tree from top to bottom III

Title Description ：

Their thinking ：

Consistent with the above question , But this question says , Even layers , Print backwards , Here we need to do the following ：

Because we The return is ret , Two dimensional array , therefore , We use it ret Size Go to % 2 , If == 0 , explain Even layers , conversely , Here we are use Double ended queue to receive For each floor Node values

The code is as follows ：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //  This question is the same as the previous one , Just pay attention here ：
        //  Even layers need to be printed backwards 
        //  The difficulty here is ： How to print in reverse , Here only need to be on the basis of the previous question 
        //  Add a   Judge  if(ret % 2 == 0)  The explanation is even , Then print in reverse 
        //  Here print backwards , We directly use the properties of double ended queues , The bottom layer of the double ended queue is  LinekdList, Linked list 
        //  here   Head insertion  addLast  Tail insertion  addFirst

        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> ret = new ArrayList<>();
        //  If  root == null  return  ret
        if(root == null) return ret;
        //  Not empty   Such as queue 
        queue.add(root);
        //  Into the loop 
        while(!queue.isEmpty()) {
            //  use  List  To receive   Each layer   The value of the node 
            LinkedList<Integer> tmp = new LinkedList<>();
            //  There are different layers ,list  Received   The number of nodes is different , So we enter the cycle 
            for(int i = queue.size();i > 0;i--) {
                TreeNode cur = queue.poll();
                //  Join judgment , Judgment is   Odd number layer   still   Even layers 
                if(ret.size() % 2 == 0) { //  The description is an even number of layers , Print backwards , Head insertion 
                    tmp.addLast(cur.val);
                }else {
                    tmp.addFirst(cur.val);
                }
                if(cur.left != null) queue.add(cur.left);
                if(cur.right != null) queue.add(cur.right);
            }
            ret.add(tmp);
        }
        return ret;
    }
}

---

Search and backtracking algorithms

The finger of the sword Offer 26. The substructure of a tree

OJ link ： The substructure of a tree

Title Description ：

Their thinking && The code is as follows ：

 //  This question , Mainly uses the nature of binary tree recursion 
 //  The meaning of the title is given ： If  B  yes  A  Of   Substructure , Express  A  There are emergence and B  Same structure and node value 

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        //  The boundary conditions ：  If  A  perhaps  B  One of them is empty , Go straight back to  false;
        //  Because the title gives , Empty numbers are not substructures of any number 
        if(A == null || B == null) return false;

        //  Judge the boundary , Next, it is divided into the following situations 
        // A  and  B  The root node of is the same , Compare their child nodes in turn 
        // 1. A  The root node   and  B  The root node of is the same , Compare their child nodes in turn 
        // 2. A  and  B  Of   The root node is different , Judge  A Whether in the left subtree of   contain  B  The root node 
        // 3. A  and  B  Of   The root node is different , Judge  A Whether in the right subtree of   contain  B  The root node 
        return isSub(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);

    }

    //  The following methods , Realization  A  and  B  The root node is the same 
    boolean isSub(TreeNode A,TreeNode B) {
        // 1.  If the traversal is finished  B, explain  B All nodes of are   and  A  On the substructure of 
        if(B == null) return true;
        // 2. A  The node in is  null ,B  The nodes in the   Not empty , explain   Mismatch 
        if(A == null) return false;
        // 3. A  and  B  It's not empty. , But the values are different , Description does not match 
        if(A.val != B.val) return false;
        //  Last , The current point is matched , Continue to recursively judge the left subtree and the right subtree , whether   Each match 
        return isSub(A.left,B.left) && isSub(A.right,B.right);
    }
}

---

The finger of the sword Offer 27. Image of binary tree

OJ link ： Image of binary tree

Title Description ：

Their thinking ：

First analyze what the topic gives Input and output , Obviously , The input is based on the sequence traversal of the binary tree , Output... Let's see , Output graph , Except for the root node , The nodes of each layer are reversed .

Understand the meaning of the question , This problem is very simple , The specific steps are as follows ：

1. Sequence traversal binary tree
2. After each stack , Exchange the values of the left and right nodes
3. return The root node

The code is as follows ：

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        //  Sequence traversal 
        Queue<TreeNode> queue = new LinkedList<>();
        //  Be careful   This question is different from the previous one , There is no need to return a binary array , One dimensional array or something , Just traverse normally 
        
        if(root == null) return null;
        queue.add(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur.left != null) {
                queue.add(cur.left);
            }
            if(cur.right != null) {
                queue.add(cur.right);
            }
            //  In exchange for 
            TreeNode tmp = cur.left;
            cur.left = cur.right;
            cur.right= tmp;
        }
        return root;
    }
}

---

The finger of the sword Offer 28. Symmetric binary tree

OJ link ： Symmetric binary tree

Title Description ：

Their thinking ：

According to the meaning , Symmetric binary tree , The specific steps are as follows ：

1. If The header node is empty return true, Empty numbers are also symmetric
2. Judge Whether the left and right subtrees symmetry
3. How to judge whether the left and right subtrees are symmetrical ？ The specific code is as follows

The code is as follows ：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        //  Termination conditions   So is the blank number   Symmetric binary tree 
        if(root == null) return true;
        //  If  root  It's not equal to   empty   return   Auxiliary method 
        return func(root.left,root.right);

    }

    //  Create methods , Judge   Whether the left and right nodes are symmetrical 
    boolean func(TreeNode L,TreeNode R) {
        //  If   Left and right nodes are empty   return TRUE
        if(L == null && R == null) return true;
        //  If   One of the left and right nodes is empty , perhaps   Around the node   inequality 
        if(L == null || R == null) return false;
        if(L.val != R.val) return false;
        //  Finally, recursive judgment  L.left = R.right L.right = R.left
        return func(L.left, R.right) && func(L.right, R.left);
    }
}

---

Search and backtracking algorithms

The finger of the sword Offer 34. The path of a value in a binary tree

OJ link ： The path of a value in a binary tree

Title Description ：

Their thinking ：

The code is as follows ：

class Solution {
    
    // DFS  Depth-first search , use   deque   preservation   route 
    //  Return a two-dimensional array 
    
    Deque<Integer> path = new LinkedList<>();
    List<List<Integer>> ret = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        DFS(root,target);
        return ret;
    }

    public void DFS(TreeNode root,int target) {
        // 1. If the header node is null, Go straight back to 
        if(root == null) return;
        // 2. Not for null, Put in  path  in 
        path.add(root.val);
        // 3. target Value minus  root.val Value 
        target -= root.val;
        // 4.  If   The root node is empty , also  target == 0, That means we're done , Put the finished path into  ret  in 
        if(root.left == null && root.right == null && target == 0) {
            //   You can't just  ret.add(path), If so  ret  Will follow  path  Change by change ,
            //  The operation here is to copy  path
            ret.add(new LinkedList<>(path));
        }
        // 5.  If you are not satisfied , Continue to search 
        DFS(root.left,target);
        DFS(root.right,target);
        // 6.  If   Added value , Out of range  
        path.pollLast();
    }
}

---

The finger of the sword Offer 36. Binary search tree and double linked list

OJ link ： Binary search tree and double linked list

Title Description ：

Their thinking && The code is as follows ：

class Solution {

    //  According to the question ： Binary search tree , The left node  <  The root node  <  Right node  -》  In the sequence traversal 

    Node pre,head;
    
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;
        DFS(root);
        //  end to end 
        pre.right = head;
        head.left = pre;
        return head;
    }

    // DFS  Search every node , And put each node   Connected to a 
    public void DFS(Node cur) {
        if(cur == null) return;
        //  In the sequence traversal 
        DFS(cur.left);
        //  Here we need to judge , If pre  It's empty , explain  head, Is the head node 
        if(pre == null) {
            head = cur;
        }else {
            //  If it's not empty , Building links 
            pre.right = cur;
        }
        cur.left = pre;
        pre = cur;
        DFS(cur.right);
    }
}

---

The finger of the sword Offer 54. The second of binary search tree k Big node

OJ link ： The second of binary search tree k Big node

Title Description ：

Their thinking && The code is as follows ：

class Solution {
    //  The core idea ： Binary search tree , The middle order traversal is incremental 
    //  So if we do the opposite   It is decreasing , Prior to joining   Counter , Not traversing a node counter ++
    //  Until the counter  == k 
    //  use  ret  receive   Return value 

    int count;
    int ret;
    public int kthLargest(TreeNode root, int k) {
        DFS(root,k);
        return ret;
    }

    void DFS(TreeNode root,int k) {
        if(root == null) return;
        DFS(root.right,k);
        count++;
        if(count == k) ret = root.val;
        DFS(root.left,k);
    }
}