[Algorithm summary] 20 questions to get the BAT interview — binary tree

This post first appeared on my personal blog: Tail-tail-fall

0. Several concepts

Complete binary tree: if the height of the binary tree is H, except for the h layer, the number of nodes of other layers (1~ H-1) reaches the maximum number, and the nodes of the h layer are continuously concentrated in the most left. Anything on your mind? In fact, a complete binary tree is closely related to a heap

Full binary tree: All nodes on each layer have two child nodes except the last layer, which is leaf nodes.

Huffman tree: given n weights as leaf nodes of N, a binary tree is constructed. If the length of weighted path reaches the minimum, such a binary tree is called an optimal binary tree, also known as Huffman tree.

Binary sort Tree: also known as Binary Search Tree. A binary sort tree is either an empty tree or a binary tree with the following properties:

• If the left subtree is not empty, the value of all nodes in the left subtree is less than the value of its root node.
• If the right subtree is not empty, the value of all nodes in the right subtree is greater than or equal to the value of its root node.
• The left and right subtrees are also binary sorting trees.
• There are no nodes with equal keys

Binary lookup is O(log(n)), and worst-case is O(n) (equivalent to sequential lookup)

Balanced binary tree: also known as AVL tree. A balanced binary tree is an evolutionary version of a binary search tree. The so-called balanced binary tree means that the absolute value of the height difference between the left and right subtrees is no more than 1.

Red-black tree: a red-black tree is a tree where each node has a color, either red or black. Red-black trees are lookup trees. Red-black trees have an important property that the longest path from the root to the leaf is no more than twice the length of the shortest path. For red-black trees, insertion, deletion, and lookup are order log N.

1. Find the number of nodes in the binary tree

Recursive solution: (1) If the binary tree is empty, the number of nodes is 0. (2) If the binary tree is not empty, the number of nodes in the binary tree = the number of nodes in the left subtree + the number of nodes in the right subtree + 1.

public static int getNodeNumRec(TreeNode root) {
        if (root == null) {
            return 0;
        }             
        return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1;
}
Copy the code

2. Find the maximum number of layers (maximum depth) of binary tree

(2) If the binary tree is not empty, the binary tree depth = Max (left subtree depth, right subtree depth) + 1

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null)
            return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right))+1; }}Copy the code

2.1 Minimum depth of binary tree

Given a Binary Tree, find the Minimum Depth of the Tree. The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node.

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null)
            return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        return (left == 0 || right == 0)? left + right +1 : Math.min(left, right) + 1; }}Copy the code

3. Preemptive traversal/preemptive traversal

LeetCode: Binary Tree Preorder Traversal

Root-left-right

recursive

ArrayList<Integer> preOrderReverse(TreeNode root){
    ArrayList<Integer> result = new ArrayList<Integer>();
    preOrder(root, result);
    return result; 
}
void preOrder(TreeNode root,ArrayList<Integer> result){
    if(root == null) {return;
    }
    result.add(root.val);
    preOrder(root.left, result);
    preOrder(root.right, result);
}
Copy the code

non-recursive

Method one:

import java.util.Stack;
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        if(root == null)
            return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(! stack.isEmpty()){ TreeNode node = stack.pop(); res.add(node.val);if(node.right ! =null){
                stack.push(node.right);
            }
            if(node.left ! =null){ stack.push(node.left); }}returnres; }}Copy the code

Method 2:

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if(root == null)
            return res;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        while(cur ! =null| |! stack.isEmpty()){if(cur! =null){
                res.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }else{ cur = stack.pop(); cur = cur.right; }}returnres; }}Copy the code

4. Middle order traversal

LeetCode: Binary Tree Inorder Traversal Returns the middle order Traversal of a given Binary Tree.

Left-root-right

recursive

void inOrder(TreeNode root,ArrayList<Integer> result){
    if(root == null) {return;
    }
    preOrder(root.left, result);
    result.add(root.val);
    preOrder(root.right, result);
}
Copy the code

non-recursive

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if(root == null)
            return res;
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        while(! stack.isEmpty() || cur ! =null) {if(cur ! =null){
                stack.push(cur);
                cur = cur.left;
            }else{ cur = stack.pop(); res.add(cur.val); cur = cur.right; }}returnres; }}Copy the code

5. Back-order traversal

Leetcode: Binary Tree Postorder Traversal Returns the sequential Traversal of a given Binary Tree.

Left-right-root

recursive

void inOrder(TreeNode root,ArrayList<Integer> result){
    if(root == null) {return;
    }
    preOrder(root.left, result);
    preOrder(root.right, result);
    result.add(root.val);
}
Copy the code

non-recursive

Method one:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> ans = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) return ans;

        stack.push(root);
        while(! stack.isEmpty()) { TreeNode cur = stack.pop();// Insert in reverse order
            ans.addFirst(cur.val);
            if(cur.left ! =null) {
                stack.push(cur.left);
            }
            if(cur.right ! =null) { stack.push(cur.right); }}returnans; }}Copy the code

Method 2:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        
        if(root == null)
            return res;
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        TreeNode visited = null;
        while(! stack.isEmpty() || cur ! =null) {if(cur ! =null){
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.peek();
                if(cur.right ! =null&& cur.right ! = visited){ cur = cur.right; }else{
                    res.add(cur.val);
                    visited = cur;
                    stack.pop();
                    cur = null; }}}returnres; }}Copy the code

Method three (recommended) :

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode p = root;
        while(! stack.isEmpty() || p ! =null) {
            if(p ! =null) {
                stack.push(p);
                result.addFirst(p.val);  // Reverse the process of preorder
                p = p.right;             // Reverse the process of preorder
            } else {
                TreeNode node = stack.pop();
                p = node.left;           // Reverse the process of preorder}}returnresult; }}Copy the code

6. Layered traversal

LeetCode: Binary Tree Level Order Traversal Offer print a Binary Tree as a given Binary Tree and return the Order Traversal of its node values.

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root == null)
            return res;
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        TreeNode cur = null;
        queue.add(root);
        
        while(! queue.isEmpty()){ ArrayList<Integer> level =new ArrayList<Integer>();
            int l = queue.size();
            for(int i=0; i<l; i++){ cur = queue.poll(); level.add(cur.val);if(cur.left ! =null)
                    queue.add(cur.left);
                if(cur.right ! =null)
                    queue.add(cur.right);
            }
            res.add(level);
        }
        returnres; }}Copy the code

6.1 Hierarchical Traversal from bottom to top

LeetCode: Binary Tree Level Order Traversal II Given a Binary Tree, return bottom-up sequential Traversal of its node values.

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null)
            return res;
        queue.add(root);
        while(! queue.isEmpty()){int count = queue.size();
            List<Integer> temp = new LinkedList<>();
            for(int i=0; i<count; i++){
                TreeNode node = queue.poll();
                temp.add(node.val);
                if(node.left ! =null)
                    queue.add(node.left);
                if(node.right ! =null)
                    queue.add(node.right);
            }
            // add to the first position each time
            res.add(0, temp);
        }
        returnres; }}Copy the code

6.2 Printing binary trees in glyph order

Implement a function to print a binary tree in zigzagging order, that is, the first line is printed from left to right, the second line is printed from right to left, the third line is printed from left to right, and so on.

Two stacks are set, s2 stores the odd-numbered layers, and S1 stores the even-numbered layers. When traversing S2 nodes, s1 is added to s1 in the order of left and right subtrees; when traversing S1 nodes, S2 is added to S2 in the order of right and left subtrees

import java.util.ArrayList;
import java.util.Stack;
/* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }} * /
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        Stack<TreeNode> s2 = new Stack<TreeNode>();
        int flag = 1;
        if(pRoot == null)
            return res;
        s2.push(pRoot);
        ArrayList<Integer> temp = new ArrayList<Integer>();
        while(! s1.isEmpty() || ! s2.isEmpty()){if(flag % 2! =0) {while(! s2.isEmpty()){ TreeNode node = s2.pop(); temp.add(node.val);if(node.left ! =null){
                        s1.push(node.left);
                    }
                    if(node.right ! =null){ s1.push(node.right); }}}if(flag % 2= =0) {while(! s1.isEmpty()){ TreeNode node = s1.pop(); temp.add(node.val);if(node.right ! =null){
                        s2.push(node.right);
                    }
                    if(node.left ! =null){
                        s2.push(node.left);
                    }
                }
            }
            res.add(new ArrayList<Integer>(temp));
            temp.clear();
            flag ++;
        }
        returnres; }}Copy the code

7. Find the number of nodes at layer K of the binary tree

void get_k_level_number(TreeNode root, int k){
    if(root == null || k <=0) {return 0;
    }
    if(root ! =null && k == 1) {return 1;
    }
    return get_k_level_number(root.left, k-1) + get_k_level_number(root.right, k-1);
}
Copy the code

8. Find the number of leaf nodes at the K layer of the binary tree

void get_k_level_leaf_number(TreeNode root, int k){
    if(root == null || k <=0) {return 0;
    }
    if(root ! =null && k == 1) {if(root.left == null && root.right == null)
            return 1;
        else
            return 0;
    }
    return get_k_level_number(root.left, k-1) + get_k_level_number(root.right, k-1);
}
Copy the code

9. Check whether the two binary trees have the same structure

Given two binary trees, write a function to check if they are the Same.

Recursive solution: (1) If two binary trees are both empty, return true (2) If two binary trees are both empty and the other is not, return false (3) If both binary trees are not empty, return true if the corresponding left and right subtrees are isomorphic, the others return false

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null)
            return true;
        if(p == null || q == null)
            return false;
        if(p.val == q.val)
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        return false; }}Copy the code

10. Determine whether a binary tree is a balanced binary tree

Given a Binary Tree, determine if it is highly Balanced. For this problem, a highly balanced binary tree is defined as: a binary tree in which the depth difference between the two subtrees of each node is no more than 1.

Recursive solution: (1) If the binary tree is empty, return true (2) if the binary tree is not empty, if the height difference between the left and right subtrees is no more than 1 and both the left and right subtrees are AVL trees, return true, others return false

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null)
            return true;
        return Math.abs(maxHigh(root.left) - maxHigh(root.right)) <= 1 
            && isBalanced(root.left) && isBalanced(root.right);
    }
    
    public int maxHigh(TreeNode root){
        if(root == null)
            return 0;
        return Math.max(maxHigh(root.left), maxHigh(root.right))+1; }}Copy the code

11. Find the mirror image of the binary tree

LeetCode: Invert Binary Tree

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null)
            return root;

        TreeNode node = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(node);
        
        returnroot; }}Copy the code

11.1 Symmetric binary trees

Given a binary Tree offer, check whether it is mirror Symmetric.

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null || isSymmetricHelper(root.left, root.right);
    }
    public boolean isSymmetricHelper(TreeNode left, TreeNode right){
        if(left == null && right == null)
            return true;
        if(left == null || right == null)
            return false;
        if(left.val ! = right.val)return false;
        returnisSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left); }}Copy the code

12. Find the lowest common ancestor node of two nodes in the binary tree

Given a Binary Tree, find the Lowest Common Ancestor (LCA) of two given nodes in the Tree.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q)
            return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left ! =null&& right ! =null)
            return root;
        return left == null? right : left; }}Copy the code

12.1 Find the nearest common ancestor of the binary search tree

LeetCode: Lowest Common Ancestor of a Binary Search Tree Given a Binary Search Tree, find the nearest 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).

The left subtree
The root node
The right subtree

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val > p.val && root.val > q.val){
            return lowestCommonAncestor(root.left, p, q);
        }
        else if(root.val < p.val && root.val < q.val){
            return lowestCommonAncestor(root.right, p, q);
        }
        else{
            returnroot; }}}Copy the code

Find the diameter of the binary tree

Given a Binary Tree, you need to calculate its Diameter. The diameter length of a binary tree is the maximum of the path length of any two nodes. This path might go through the root.

class Solution {
    private int path = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        diamHelper(root);
        return path;
    }
    
    private int diamHelper(TreeNode root){
        if(root == null)
            return 0;
        int left = diamHelper(root.left);
        int right = diamHelper(root.right);
        path = Math.max(path, left + right);
        return Math.max(left, right) + 1; }}Copy the code

14. Rebuild binary tree from pre-order traversal sequence and middle-order traversal sequence

LeetCode: Construct Binary Tree from Preorder and Inorder Traversal Construct Binary Tree from Preorder and Inorder Traversal

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 || inorder.length == 0)
            return null;
        return buildTreeHelper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }
    
    public TreeNode buildTreeHelper(int[] preorder, int pre_start, int pre_end, 
                                    int[] inorder, int in_start, int in_end){
        if(pre_start > pre_end || in_start > in_end)
            return null;
        TreeNode root = new TreeNode(preorder[pre_start]);
        for(int i = in_start; i <= in_end; i++){
            if(inorder[i] == preorder[pre_start]){
                // Left subtree length: i-is
                root.left = buildTreeHelper(preorder, pre_start + 1, pre_start + i - in_start, inorder, in_start, i - 1);
                root.right = buildTreeHelper(preorder, pre_start + i - in_start + 1, pre_end, inorder, i + 1, in_end); }}returnroot; }}Copy the code

14.1 Construct a binary tree by traversing sequences in middle and rear order

Construct Binary Tree from Inorder and Postorder Traversal Construct Binary Tree from Inorder and Postorder Traversal

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder.length == 0 || postorder.length == 0)
            return null;
        return buildTreeHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }
            
    public TreeNode buildTreeHelper(int[] inorder, int in_start, int in_end, 
                               int[] postorder, int post_start, int post_end){
        if(in_start > in_end || post_start > post_end)
            return null;
        TreeNode root = new TreeNode(postorder[post_end]);
        for(int i = in_start; i <= in_end; i++){
            if(inorder[i] == postorder[post_end]){
                root.left = buildTreeHelper(inorder, in_start, i - 1, postorder, post_start, post_start + i - in_start - 1);
                root.right = buildTreeHelper(inorder, i + 1, in_end, postorder, post_start + i - in_start, post_end - 1); }}returnroot; }}Copy the code

Tip: It is not possible to construct a unique binary tree based on pre-order and post-order traversal

15. Determine whether a binary tree is a complete binary tree

A complete binary tree is one in which the left side of the last layer is full, the right side may be slow and full, and then the rest of the layers are full. According to this property, layer traversal is used. If we are currently traversing NULL nodes, and if there are non-null nodes following, it is not a complete binary tree.

class Solution {
    public boolean _CheckCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = LinkedList<>();
        if(root == null)
            return true;
        queue.add(root);
        while(! queue.isEmpty()){ TreeNode node = queue.pop();if(node ! =null) {if(flag == true)
                    return false;
                queue.add(node.left);
                queue.add(node.right);
            }else{
                flag = true; }}return true; }}Copy the code

16. Tree substructure

Input two binary trees A and B to determine whether B is A substructure of A.

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1 == null || root2 == null) {return false;
        }
        return IsSubtree(root1, root2) || 
               HasSubtree(root1.left, root2) ||
               HasSubtree(root1.right, root2);
    }
    public boolean IsSubtree(TreeNode root1, TreeNode root2){
        / / must first determine roo2, or {8,8,7,9,2, #, #, #, #, 4, 7}, {8,9,2} the test case.
        if(root2 == null)
            return true;
        if(root1 == null)
            return false;
        if(root1.val == root2.val){
            return IsSubtree(root1.left, root2.left) && 
                IsSubtree(root1.right, root2.right);
        }else
            return false; }}Copy the code

17. Binary tree neutral path of a certain value

Offer: Input a binary tree and an integer and print out the sum of node values in the binary tree as all paths of input integers. A path is defined as a path from the root of the tree down to the nodes passed by the leaf.

public class Solution {
    ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
    ArrayList<Integer> temp = new ArrayList<Integer>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        if(root == null)
            return res;
        target -= root.val;
        temp.add(root.val);
        if(target == 0 && root.left == null && root.right == null)
            res.add(new ArrayList<Integer>(temp));
        else{
            FindPath(root.left, target);
            FindPath(root.right, target);
        }
        temp.remove(temp.size()-1);
        returnres; }}Copy the code

The next node of the binary tree

Given a binary tree and one of its nodes, please find the next node in the middle order traversal order and return. Note that the nodes in the tree contain not only the left and right children, but also Pointers to the parent.

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode == null) {return null;
        }
        if(pNode.right ! =null){
            TreeLinkNode node = pNode.right;
            while(node.left ! =null){
                node = node.left;
            }
            return node;
        }
        while(pNode.next ! =null){
            TreeLinkNode root = pNode.next;
            if(pNode == root.left)
                return root;
            pNode = root;
        }
        return null; }}Copy the code

Serialize binary trees

LeetCode: Serialize and Deserialize Binary Tree Implement two functions to Serialize and Deserialize Binary Tree

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null)
            return # ",";
        StringBuffer res = new StringBuffer(root.val + ",");
        res.append(serialize(root.left));
        res.append(serialize(root.right));
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String [] d = data.split(",");
        Queue<String> queue = new LinkedList<>();
        for(int i = 0; i < d.length; i++){
            queue.offer(d[i]);
        }
        return pre(queue);
    }
    
    public TreeNode pre(Queue<String> queue){
        String val = queue.poll();
        if(val.equals("#"))
            return null;
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = pre(queue);
        node.right = pre(queue);
        returnnode; }}Copy the code

20. The KTH node of the binary search tree

Given a binary search tree, find the KTH smallest node. For example, in (5,3,7,2,4,6,8), the value of the third summary point in order of node numerical size is 4.

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        if(root == null)
             return Integer.MIN_VALUE;
        Stack<TreeNode> stack = new Stack<>();
        int count = 0;
        TreeNode p = root;
        while(p ! =null| |! stack.isEmpty()){if(p ! =null){
                stack.push(p);
                p = p.left;
            }else{
                TreeNode node = stack.pop();
                count ++;
                if(count == k)
                    returnnode.val; p = node.right; }}returnInteger.MIN_VALUE; }}Copy the code