My CSDN blog: blog.csdn.net/gdutxiaoxu my nuggets: juejin. Cn/user / 220747… Making: github.com/gdutxiaoxu/ WeChat public number: programmers Xu Gong (stormjun94) on zhihu: www.zhihu.com/people/xuju…

preface

Some time ago, I wrote a series of articles necessary for the interview, and I got a good response. Some readers asked if they could sort out some common interview algorithms. A while back, I happened to summarize LeetCode’s common interview algorithm questions.

HTTP and HTTPS

Basic knowledge of computer networking (TCP, UDP, Http, HTTPS)

Android interview essentials – Threads

JVM and class loading mechanism

Android Interview prerequisites – System, App, Activity startup process

Interviewer Series – Do you really know HTTP

The interviewer asks, is HTTPS really secure, can you capture packets, and how to prevent packet capture

Java version of the Sword finger Offer algorithm collection

LeetCode linked list of knowledge points & questions type summary

Android_interview making address

At the beginning of the preparation of brush algorithm topic, feeling really is very difficult, ten topics have nine is not. In the heart of ten thousand grass mud horse ran, how so hot chicken.

Over time, I discovered that algorithms are also one that can grow with practice.

First of all, we need to master the basic data structure, array, linked list, hash table, Set, binary tree, heap, stack and so on. You need to know what their strengths and weaknesses are, what their scenarios are, what their time and space complexity is. You don’t know the simple API.
And then, once you’ve mastered these basic data structures, there are some basic algorithms that you need to know, like quicksort, merge sort, pair sort, binary search. These basic things must be mastered and are often asked in interviews.
Classification brush problem, we can see above the force buckle, leetcode-cn.com/problemset/… , brush questions can be according to the label. Such as linked lists, arrays, binary search, binary trees, dynamic programming and so on
Learning algorithm is not a day’s work, need long-term accumulation. The recommended practice is to do one or two questions a day, not many questions, but understanding. Stick with it for a month or two, and you’ll start to feel better

No more nonsense, began to enter the body of today, LeetCode linked list knowledge points & questions summary

The idea of a binary tree

A Binary Tree is a finite set of n nodes that is either empty (in this case, the Binary Tree is called an empty Tree) or consists of a root node and two disjoint Binary trees called left and right subtrees, respectively, of the root node.

A typical binary tree is shown below:

It can be seen from the above definition that a node in a binary tree contains at most two subtrees, called left and right subtrees respectively, and the left and right subtrees contain at most two subtrees respectively. From the above definition, the definition of binary tree is a recursive definition.

Binary tree species

Full binary tree

For a binary tree, a binary tree is called full if every non-leaf node has left and right subtrees and all leaf nodes in the tree are in the same layer.

Complete binary tree

A binary tree with N nodes is numbered according to the hierarchy, and the left and right subtrees are numbered first left and then right. If the node numbered I is in exactly the same position in the binary tree as the node numbered I in the full binary tree with the same depth, the binary tree is called a complete binary tree.

Binary sort tree:

Binary Search Tree (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 and black tree:

A red-black tree is a tree where every node is colored, either red or black, and a red-black tree is a lookup tree. 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.

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.

Traverse the way

There are four main traversal methods for binary trees

Sequential (root-first) traversal: Visits the root node first, then the left and right children
Middle-order traversal: Access the child first, then the root node and the right child
Back-order traversal: access the left child first, then the right child, then the root node
Layer traversal: Traversal from bottom to top based on the number of layers

Premise: The binary tree structure in the test is presented here, as shown in the figure below

The order of results of several traversal modes corresponding to the binary tree is as follows:

Sequential traversal: 10->6->4->8->14->12->16
Middle order traversal: 4->6->8->10->12->14->16
Backorder traversal: 4->8->6->12->16->14->10
Level traversal: 10->6->14->4->8->12->16

recursive

A tree is either empty or has two Pointers, each pointing to a tree. A tree is a recursive structure and many tree problems can be handled recursively.

1. Tree height

1.0 Finding the maximum number of layers (maximum depth) of binary tree

104. Maximum Depth of Binary Tree (Easy)

Leetcode/power button

The solution to this problem is actually quite simple

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

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
Copy the code

1.1 Minimum depth of binary tree

LeetCode: Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node.

Their thinking

For a node, if either the left or right subtrees are empty, the minimum depth is left + right + 1
If neither left nor right subtrees are empty, then the minimum depth is math.min (left,right) + 1

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

2. Balanced tree

110. Balanced Binary Tree (Easy)

Leetcode/power button

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Train of thought

The height difference between the left and right subtrees of a balanced tree is less than or equal to 1

private boolean result = true;

public boolean isBalanced(TreeNode root) {
    maxDepth(root);
    return result;
}

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    int l = maxDepth(root.left);
    int r = maxDepth(root.right);
    if (Math.abs(l - r) > 1) result = false;
    return 1 + Math.max(l, r);
}
Copy the code

3. The longest path between two nodes

543. Diameter of Binary Tree (Easy)

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 may or may not go through the root.

Leetcode/power button

Input:

         1
        / \
       2  3
      / \
     4   5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
Copy the code

Their thinking

Since the longest diameter does not necessarily cross the root node, the longest path needs to be calculated with each node as the center.
Use a global variable Max to maintain the longest path (depth of left subtree + depth of right subtree).
To calculate the depth of each subtree, calculate the depth of each node in the tree using depth-first traversal (Max (left subtree depth, right subtree depth))

private int max = 0;

public int diameterOfBinaryTree(TreeNode root) {
    depth(root);
    return max;
}

private int depth(TreeNode root) {
    if (root == null) return 0;
    int leftDepth = depth(root.left);
    int rightDepth = depth(root.right);
    max = Math.max(max, leftDepth + rightDepth);
    return Math.max(leftDepth, rightDepth) + 1;
}
Copy the code

4. Turn the tree

226. Invert Binary Tree (Easy)

Leetcode/power button

Ideas and Algorithms

This is a classic binary tree problem. Obviously, we start at the root, recursively traverse the tree, and flip from the leaf first.
If the left and right subtrees of the node root have been flipped, then we only need to switch the positions of the two subtrees to complete the flipping of the entire subtree with root as the root node.

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode left = root.left;  // The next operation will change the left pointer, so save it for now
    root.left = invertTree(root.right);
    root.right = invertTree(left);
    return root;
}
Copy the code

5. Merge two trees

617. Merge Two Binary Trees (Easy)

Leetcode/power button

Given two binary trees, imagine that when you overlay one of them on top of the other, some nodes of the two binary trees will overlap.

You need to merge them into a new binary tree. The rule for merging is that if two nodes overlap, their values are added as the new value of the nodes merged, otherwise a node that is not NULL is directly added as a node in the new binary tree

Input:
       Tree 1                     Tree 2
          1                         2
         / \                       / \
        3   2                     1   3
       /                           \   \
      5                             4   7

Output:
         3
        / \
       4   5
      / \   \
     5   4   7
Copy the code

public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return null;
    if (t1 == null) return t2;
    if (t2 == null) return t1;
    TreeNode root = new TreeNode(t1.val + t2.val);
    root.left = mergeTrees(t1.left, t2.left);
    root.right = mergeTrees(t1.right, t2.right);
    return root;
}
Copy the code

6. Check whether the sum of paths equals a number

Leetcdoe : 112. Path Sum (Easy)

Leetcode/power button

Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
Copy the code

The path sum is defined as the sum of all nodes from root to leaf.

public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) return false;
    if (root.left == null && root.right == null && root.val == sum) return true;
    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
Copy the code

7. Count the number of paths and paths equal to a number

437. Path Sum III (Easy)

Leetcode/power button

Root = [10, 5, 3 31, null, 11, 3, 2, null, 1]. sum = 8 10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1 Return 3. The paths that sum to 8 are: 1. 5 -> 3 2. 5 -> 2 -> 1 3Copy the code

Paths do not have to start with root or end with leaf, but they must be continuous.

public int pathSum(TreeNode root, int sum) {
    if (root == null) return 0;
    int ret = pathSumStartWithRoot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    return ret;
}

private int pathSumStartWithRoot(TreeNode root, int sum) {
    if (root == null) return 0;
    int ret = 0;
    if (root.val == sum) ret++;
    ret += pathSumStartWithRoot(root.left, sum - root.val) + pathSumStartWithRoot(root.right, sum - root.val);
    return ret;
}
Copy the code

8. Subtree

572. Subtree of Another Tree (Easy)

Leetcode/power button

Given tree s:
     3
    / \
   4   5
  / \
 1   2

Given tree t:
   4
  / \
 1   2

Return true, because t has the same structure and node values with a subtree of s.

Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0

Given tree t:
   4
  / \
 1   2

Return false.
Copy the code

Their thinking

To determine whether a tree T is a subtree of s, we can determine whether T is equal to any subtree of S. So convert to 100. Same Tree. So what we’re doing here is at each child of S, we’re trying to determine whether that child is equal to t.

The three conditions for judging whether two trees are equal are the relation between and, namely:

The root nodes of the current two trees are equal;

And the left subtree of S is equal to the left subtree of T;
And the right subtree of S is equal to the right subtree of T.
And the three conditions for judging whether T is a subtree of S are the relation of or, namely:

Currently two trees are equal;

Or t is the left subtree of S;
Or t is the right subtree of S.
The code that determines whether a tree is equal or not is a subtree is pretty symmetric

Leetcode-cn.com/problems/su…

public boolean isSubtree(TreeNode s, TreeNode t) {
    if (s == null) return false;
    return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}

private boolean isSubtreeWithRoot(TreeNode s, TreeNode t) {
    if (t == null && s == null) return true;
    if (t == null || s == null) return false;
    if(t.val ! = s.val)return false;
    return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right);
}
Copy the code

9. Symmetry of trees

101. Symmetric Tree (Easy)

Leetcode/power button

public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isSymmetric(root.left, root.right);
}

private boolean isSymmetric(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return true;
    if (t1 == null || t2 == null) return false;
    if(t1.val ! = t2.val)return false;
    return isSymmetric(t1.left, t2.right) && isSymmetric(t1.right, t2.left);
}
Copy the code

Find the mirror image of the binary tree

class Solution { public TreeNode invertTree(TreeNode root) { if(root == null) return root; TreeNode node = root.left; invertTree = invertTree; root.left = invertTree(root.right); root.right = invertTree(node); return root; }}Copy the code

11. Minimum path

111. Minimum Depth of Binary Tree (Easy)

Leetcode/power button

The minimum path length from root to leaf of a tree

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

Level traversal

Use BFS for hierarchical traversal. There is no need to use two queues to store the nodes of the current layer and the nodes of the next layer respectively, because when traversing the nodes of the first layer, the number of nodes in the current queue is the number of nodes of the current layer. As long as the number of nodes traversed is controlled, it can ensure that all nodes of the current layer are traversed this time.

1. Sequence traversal of binary tree

Sequence traversal of binary trees II

Given a binary tree, returns a 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

Print the binary tree in zigzags

Finger offer: Prints binary tree in zigzag 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.

Set two stacks, S2 to store the odd-numbered layer, s1 to store the even-numbered layer
When traversing S2 nodes, s1 is added in the order of left and right subtrees.
When traversing s1 nodes, s2 is added 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 ++; } return res; }}Copy the code

Order traversal before, middle and after

1 / \ 2 3 / \ 4 5 6Copy the code

Hierarchical traversal order: [1, 2, 3, 4, 5, 6]
[1, 2, 4, 5, 3, 6]
Middle order traversal order: [4 2 5 1 3 6]
After order traversal order: [4 5 2 6 3 1]

Hierarchical traversal using BFS implementation, the use of BFS layer by layer traversal characteristics; DFS is used to realize pre-order, middle-order and post-order traversal.

Pre-order, mid-order and post-order traversal are the same except for the order in which nodes are accessed.

1) before the order

void dfs(TreeNode root) {
    visit(root);
    dfs(root.left);
    dfs(root.right);
}
Copy the code

(2) in the sequence

void dfs(TreeNode root) {
    dfs(root.left);
    visit(root);
    dfs(root.right);
}
Copy the code

(3) after the order

void dfs(TreeNode root) {
    dfs(root.left);
    dfs(root.right);
    visit(root);
}
Copy the code

1. Non-recursive implementation of binary tree preorder traversal

144. Binary Tree Preorder Traversal (Medium)

Leetcode/power button

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while(! stack.isEmpty()) { TreeNode node = stack.pop();if (node == null) continue;
        ret.add(node.val);
        stack.push(node.right);  // Make sure the left subtree is traversed first
        stack.push(node.left);
    }
    return ret;
}
Copy the code

2. Non-recursive implementation of binary tree after the order traversal

145. Binary Tree Postorder Traversal (Medium)

Leetcode/power button

The preceding traversal is root -> left -> right, and the latter is left -> right -> root. You can change the pre-order traversal to root -> right -> left so that the order is reversed from the post-order traversal.

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while(! stack.isEmpty()) { TreeNode node = stack.pop();if (node == null) continue;
        ret.add(node.val);
        stack.push(node.left);
        stack.push(node.right);
    }
    Collections.reverse(ret);
    return ret;
}
Copy the code

3. Non-recursive implementation of binary tree middle order traversal

94. Binary Tree Inorder Traversal (Medium)

Leetcode/power button

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
    if (root == null) return ret;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while(cur ! =null| |! stack.isEmpty()) {while(cur ! =null) {
            stack.push(cur);
            cur = cur.left;
        }
        TreeNode node = stack.pop();
        ret.add(node.val);
        cur = node.right;
    }
    return ret;
}
Copy the code

BST

Binary search tree (BST) : The root node is greater than or equal to all nodes in the left subtree and less than or equal to all nodes in the right subtree.

Order traversal in a binary search tree.

1. Trim the binary lookup tree

669. Trim a Binary Search Tree (Easy)

Leetcode/power button

Input:

    3
   / \
  0   4
   \
    2
   /
  1

  L = 1
  R = 3

Output:

      3
     /
   2
  /
 1
Copy the code

Only nodes between L and R are reserved

public TreeNode trimBST(TreeNode root, int L, int R) {
    if (root == null) return null;
    if (root.val > R) return trimBST(root.left, L, R);
    if (root.val < L) return trimBST(root.right, L, R);
    root.left = trimBST(root.left, L, R);
    root.right = trimBST(root.right, L, R);
    return root;
}
Copy the code

2. Find the KTH element of the binary search tree

230. Kth Smallest Element in a BST (Medium)

Leetcode/power button

Middle order traversal solution:

private int cnt = 0;
private int val;

public int kthSmallest(TreeNode root, int k) {
    inOrder(root, k);
    return val;
}

private void inOrder(TreeNode node, int k) {
    if (node == null) return;
    inOrder(node.left, k);
    cnt++;
    if (cnt == k) {
        val = node.val;
        return;
    }
    inOrder(node.right, k);
}
Copy the code

Recursive solution:

public int kthSmallest(TreeNode root, int k) {
    int leftCnt = count(root.left);
    if (leftCnt == k - 1) return root.val;
    if (leftCnt > k - 1) return kthSmallest(root.left, k);
    return kthSmallest(root.right, k - leftCnt - 1);
}

private int count(TreeNode node) {
    if (node == null) return 0;
    return 1 + count(node.left) + count(node.right);
}
Copy the code

3. Add the value of each node in the binary search tree to the value of the node larger than it

Convert BST to Greater Tree (Easy)

Leetcode/power button

Input: The root of a Binary Search Tree like this:

              5
            /   \
           2     13

Output: The root of a Greater Tree like this:

             18
            /   \
          20     13
Copy the code

Let’s go through the right subtree.

private int sum = 0;

public TreeNode convertBST(TreeNode root) {
    traver(root);
    return root;
}

private void traver(TreeNode node) {
    if (node == null) return;
    traver(node.right);
    sum += node.val;
    node.val = sum;
    traver(node.left);
}
Copy the code

4. The most recent common ancestor of the binary lookup tree

235. Lowest Common Ancestor of a Binary Search Tree (Easy)

Leetcode/power button

        _______6______
      /                \
  ___2__             ___8__
 /      \           /      \
0        4         7        9
        /  \
       3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
Copy the code

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

5. The most recent common ancestor of binary trees

236. Lowest Common Ancestor of a Binary Tree (Medium)

Leetcode/power button

       _______3______
      /              \
  ___5__           ___1__
 /      \         /      \
6        2       0        8
        /  \
       7    4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Copy the code

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);
    return left == null ? right : right == null ? left : root;
}
Copy the code

Construct a binary lookup tree from an ordered array

108. Convert Sorted Array to Binary Search Tree (Easy)

Leetcode/power button

public TreeNode sortedArrayToBST(int[] nums) {
    return toBST(nums, 0, nums.length - 1);
}

private TreeNode toBST(int[] nums, int sIdx, int eIdx){
    if (sIdx > eIdx) return null;
    int mIdx = (sIdx + eIdx) / 2;
    TreeNode root = new TreeNode(nums[mIdx]);
    root.left =  toBST(nums, sIdx, mIdx - 1);
    root.right = toBST(nums, mIdx + 1, eIdx);
    return root;
}
Copy the code

7. Construct balanced binary search tree based on ordered list

109. Convert Sorted List to Binary Search Tree (Medium)

Leetcode/power button

Given the sorted linked list: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10, NULL,5], which teaches the following height balanced BST: 0 / \ -3 9 / / -10 5Copy the code

public TreeNode sortedListToBST(ListNode head) {
    if (head == null) return null;
    if (head.next == null) return new TreeNode(head.val);
    ListNode preMid = preMid(head);
    ListNode mid = preMid.next;
    preMid.next = null;  // Break the linked list
    TreeNode t = new TreeNode(mid.val);
    t.left = sortedListToBST(head);
    t.right = sortedListToBST(mid.next);
    return t;
}

private ListNode preMid(ListNode head) {
    ListNode slow = head, fast = head.next;
    ListNode pre = head;
    while(fast ! =null&& fast.next ! =null) {
        pre = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    return pre;
}
Copy the code

8. Find two nodes in the binary search tree and make their sum a given value

653. Two Sum IV – Input is a BST (Easy)

Leetcode/power button

Input:

    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True
Copy the code

After the ordered array is obtained by middle order traversal, the double pointer is used to search the array.

It should be noted that this problem cannot handle this idea in terms of two parts of the left and right subtrees, since the two nodes to be found may be in the left and right subtrees.

public boolean findTarget(TreeNode root, int k) {
    List<Integer> nums = new ArrayList<>();
    inOrder(root, nums);
    int i = 0, j = nums.size() - 1;
    while (i < j) {
        int sum = nums.get(i) + nums.get(j);
        if (sum == k) return true;
        if (sum < k) i++;
        else j--;
    }
    return false;
}

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

9. Find the minimum absolute value of the difference between two nodes in the binary search tree

530. Minimum Absolute Difference in BST (Easy)

Leetcode/power button

Input:

   1
    \
     3
    /
   2

Output:

1
Copy the code

Using the order property of middle order traversal of binary search tree, the absolute value of difference between two adjacent nodes in middle order traversal is calculated and the minimum value is taken.

private int minDiff = Integer.MAX_VALUE;
private TreeNode preNode = null;

public int getMinimumDifference(TreeNode root) {
    inOrder(root);
    return minDiff;
}

private void inOrder(TreeNode node) {
    if (node == null) return;
    inOrder(node.left);
    if(preNode ! =null) minDiff = Math.min(minDiff, node.val - preNode.val);
    preNode = node;
    inOrder(node.right);
}
Copy the code

10. Find the most frequent value in the binary lookup tree

501. Find Mode in Binary Search Tree (Easy)

Leetcode/power button

   1
    \
     2
    /
   2

return [2].
Copy the code

There may be more than one answer, which means that multiple values occur equally many times.

private int curCnt = 1;
private int maxCnt = 1;
private TreeNode preNode = null;

public int[] findMode(TreeNode root) {
    List<Integer> maxCntNums = new ArrayList<>();
    inOrder(root, maxCntNums);
    int[] ret = new int[maxCntNums.size()];
    int idx = 0;
    for (int num : maxCntNums) {
        ret[idx++] = num;
    }
    return ret;
}

private void inOrder(TreeNode node, List<Integer> nums) {
    if (node == null) return;
    inOrder(node.left, nums);
    if(preNode ! =null) {
        if (preNode.val == node.val) curCnt++;
        else curCnt = 1;
    }
    if (curCnt > maxCnt) {
        maxCnt = curCnt;
        nums.clear();
        nums.add(node.val);
    } else if (curCnt == maxCnt) {
        nums.add(node.val);
    }
    preNode = node;
    inOrder(node.right, nums);
}
Copy the code

Refer to the article

Leetcode – Tree

summary

If you want to learn the algorithm, I suggest you brush all of the above binary trees. If you just want to prepare for an interview, focus on the frequently asked questions.

Recursion of the tree. The depth of the tree, the minimum depth, the mirror image of the tree.
Pre-order traversal, middle-order traversal, and subsequent traversal of a binary tree, remember, both recursive and non-recursive solutions. Learn to draw inferences.
Binary tree order traversal, recursive and non-recursive also need to be able to.
Common BST algorithm. The nearest common ancestor of a binary lookup tree (two elements, three elements, multiple elements). The most recent common ancestor of a binary tree.

If you find it helpful, please help start Android_interview github. Or follow my wechat public number, Xu Gong Code Word

Click scan to follow

【 Algorithm summary 】30 questions to solve the big factory algorithm interview – binary tree

preface

The idea of a binary tree

Binary tree species

Traverse the way

recursive

1. Tree height

1.0 Finding the maximum number of layers (maximum depth) of binary tree

1.1 Minimum depth of binary tree

2. Balanced tree

Train of thought

3. The longest path between two nodes

4. Turn the tree

5. Merge two trees

6. Check whether the sum of paths equals a number

7. Count the number of paths and paths equal to a number

8. Subtree

Their thinking

9. Symmetry of trees

Find the mirror image of the binary tree

11. Minimum path

Level traversal

1. Sequence traversal of binary tree

Print the binary tree in zigzags

Order traversal before, middle and after

1. Non-recursive implementation of binary tree preorder traversal

2. Non-recursive implementation of binary tree after the order traversal

3. Non-recursive implementation of binary tree middle order traversal

BST

1. Trim the binary lookup tree

2. Find the KTH element of the binary search tree

3. Add the value of each node in the binary search tree to the value of the node larger than it

4. The most recent common ancestor of the binary lookup tree

5. The most recent common ancestor of binary trees

Construct a binary lookup tree from an ordered array

7. Construct balanced binary search tree based on ordered list

8. Find two nodes in the binary search tree and make their sum a given value

9. Find the minimum absolute value of the difference between two nodes in the binary search tree

10. Find the most frequent value in the binary lookup tree

Refer to the article

summary

Related Posts

Global Overseas/Foreign IP Proxy (HTTP/HTTPS/SOcks5)

Asynchronous processing in Android and iOS development (iii) — Multiple asynchronous tasks collaborate

Android static scan analysis