Like attention, no more lost, your support means a lot to me!

🔥 Hi, I’m Chouchou. GitHub · Android-Notebook has been included in this article. Welcome to grow up with Chouchou Peng. (Contact information at GitHub)

directory

1. An overview of the

A good algorithm often depends on the data structure used. In algorithm interviews, there are usually several basic data structures involved. Among them, Tree is the most frequently tested, but also relatively difficult. It is suggested that candidates prepare the interview questions about trees first.

1.1 Logical Structure

Logically, a Tree is a nonlinear structure. The nodes of the Tree contain the element values and a list of all the child nodes. According to graph theory, tree can be regarded as a special graph (a connected directed acyclic graph with N nodes and N-1 edges).

1.2 Storage Structure

In terms of storage, trees can be stored in two ways: array and linked list. The linked list storage method is very straightforward, that is, each node holds the reference of the child node, while the array storage method needs to use the subscript to find the parent-child node relationship, so the node does not need to hold the reference of the child node, which is more memory saving.

In the array storage mode, the root node of the tree can be assigned to the [0] bit or the [1] bit of the array. There is no obvious difference between the two methods, mainly because the formula for calculating the subscripts of the child node/parent node is different:

The root node is stored in bit [0]

  1. For nodes on bit [I], bit [2 * I +1] is the left node and bit [2 * I + 2] is the right node
  2. For nodes on bit [I], bit [(i-1) / 2] is the parent node

The root node is stored in bit [1]

  1. Bit [0] is not stored; the root node is stored in bit [1]
  2. For nodes on bit [I], bit [2 * I] is the left node and bit [2 * I + 1] is the right node
  3. For nodes on bit [I], bit [I / 2] is the parent node

It should be noted that the full binary tree using array storage is the most efficient space.

– reference time.geekbang.org/column/arti… For the king

2. Tree traversal

Tree traversal is the most important knowledge of trees, but also the point of examination, because when solving other problems, we usually need to traverse the whole tree to find the answer, so we must be very familiar with the tree traversal methods (especially binary tree traversal). To summarize common topics, we can divide the ways of traversing a tree into:

  • Preorder traversal (DFS)
  • Middle order traversal (DFS)
  • Post-order traversal (DFS)
  • Sequence traversal (BFS)
  • Path traversal (popular)
  • Vertical traversal (unpopular)

— quoted from LeetCode

2.1 Pre-order traversal & middle-order traversal & post-order traversal

The difference between the three traversals is that when a node is accessed, the current node is processed in a different order than the left and right subtrees. In a front-order traversal, the order in which nodes are accessed is consistent with the order in which nodes are processed, while the other two are inconsistent.

Preorder (root) {
  1. access content of root 
  2. Call Preorder(root.left)
  3. Call Preorder(root.right)
}

Postorder (root) {
  1. Call Postorder(root.left)
  2. Call Postorder(root.right)
  3. access content of root
}

Inorder (root) {
  1. Call Inorder(root.left) 
  2. access content of root
  3. Call Inorder(root.right)
}
Copy the code
  • The recursive method

The recursive solution can be said to be very simple, is to adjust the recursive order of the left and right subtrees:

  • Non-recursive solution

The non-recursive solution of BFS takes advantage of the LIFO feature of the stack:

Complexity analysis:

  • Time complexity: O(n)O(n)O(n)

  • Space complexity: worst O(n)O(n)O(n) O(n)O(n)O(n) O(n)O(n)O(n) O(n)O(n)O(n) O(n)O(n)O(n) O(n)O(n)O(n) O(n)O

2.2 Sequence traversal

Sequential traversal needs to make use of the FIFO feature of queues, that is, each iteration puts a whole layer of nodes into queues, as shown in the figure below:

— quoted from leetcode-cn.com/problems/bi… The nettee

fun levelOrder(root: TreeNode?) : List<List<Int>> { val result = ArrayList<List<Int>>() val queue: Queue<TreeNode> = LinkedList() if (null ! = root) { queue.offer(root) } while (! Queue. IsEmpty () {val level = ArrayList<Int>() for (index in 0 until queue.size) {val node = queue.poll() level.add(node.`val`) if (null ! = node.left) { queue.offer(node.left) } if (null ! = node.right) { queue.offer(node.right) } } if (level.isNotEmpty()) { result.add(level) } } return result }Copy the code

In addition, sequence traversal is also a common variation problem, such as bottom-up and zigzag, which is nothing more than the steps to change the output result:

- Zigzag: var flag = true for(...) { if(flag){ level.add(node.`val`) }else{ level.addFirst(node.`val`) } } ... flag = ! Flag - Bottom-up: for(...) {... } result.addFirst(level)Copy the code

Complexity analysis:

  • Time complexity: O(n)O(n)O(n)
  • Space complexity: worst O(n)O(n)O(n) O(n)O(n)O(n) O(n)O(n)O(n) O(n)O(n)O(n) O(n)O(n)O(n) O(n)O(n)O(n) O(n)O

2.3 Path Traversal

Path traversal is an updated version of the previous four types of traversal, which simply record the passing nodes to a String. The following DFS solution uses the simplest preorder traversal method:

Complexity analysis:

  • O(n2)O(n^2)O(n2)
  • Worst chain table space complexity: tree degradation O (n2) to O (n ^ 2) O (n2), the optimal tree equilibrium O ((LGN) 2) O ((LGN) ^ 2) O (2) (LGN), average O ((LGN) 2) O ((LGN) ^ 2) O ((LGN) 2)

2.4 Vertical traversal

Editting…

  • Corresponding topics in this section:

    • 987. Vertical Order Traversal of a Binary Tree

3. The concept of trees

Tree-related concepts are not usually examined directly, but understanding them is the basis for solving other complex problems.

– reference time.geekbang.org/column/arti… For the king

  • 3. A passing node from one node to another;
  • Distance: usually refers to the shortest distance, that is, the path sum of two nodes to the nearest common ancestor;
  • Height: path from node to leaf node;
  • Depth: path from node to root node;
  • Width: The length between two endpoints of each layer (the left-most and right-most non-empty nodes of the layer, with null nodes between the two endpoints also counted as length).

4. Recursive thinking

Often, in order for a tree to satisfy a certain property, it is required that every node of the tree also satisfy the property. For example, for a binary search tree, every subtree of the tree is a binary search tree. Or, when solving the final solution of a tree, the final solution of the left and right subtrees can be obtained first, and then the final solution can be obtained by combining the current node.

General solution template & ideas are as follows:

Var result = integer.min_value or 0 fun Search (node: TreeNode) : Int{1. Val leftResult = search(node.left) 2. Val rightResult = search(node.right) 3. The current solution val bestResult =... 5. Return current result}Copy the code

For example, find the maximum depth of a binary tree. We want to find the maximum depth of a tree, and if we know the maximum depth of the left and right subtrees, then obviously the maximum depth of the tree is going to be the maximum of the two subtrees plus one. So this problem can be easily solved by recursion, and of course by sequential traversal:

Fun maxDepth(root: TreeNode?) : Int { if (root == null) { return 0 } else { val leftHeight = maxDepth(root.left) val rightHeight = maxDepth(root.right) Max (leftHeight, rightHeight) + 1}} fun maxDepth(root: TreeNode? : Int { fun search(root: TreeNode? , parentDepth: Int): Int { if (root == null) { return parentDepth } else { val leftHeight = search(root.left, parentDepth + 1) val rightHeight = search(root.right, parentDepth + 1) return Math.max(leftHeight, rightHeight) } } return search(root, 0) }Copy the code

While these two pieces of code look similar, they are fundamentally different. In reference 1, + is performed on the child node, while in reference 2, + is performed on the parent node. In other words, reference code 1 is more suitable for the idea of “integrating the solution of the subproblem to get the final solution”, while reference code 2 is more suitable for the idea of “passing the state of the parent node to the child node”.

5. Path problems

Earlier we defined the concept of a path: a passing node that goes from one node to another. In this section we will focus on path-related issues.

5.1 Downward Path (Root to leaf path)

This type of problem finds a path that satisfies a certain condition, requiring that the path is from the root node to the leaf node. This specifies the start and end points of a path, so such problems can be easily solved by following section 2.3 – Path traversal.

5.2 Downward paths (not necessarily root to leaf paths)

This type of problem does not require a path from the root node to the leaf node, which may or may not go through. So the starting and ending points of the path are a little bit more difficult, so how do you solve it? This brings us to the concept of prefix sums.

Assuming we want to find A path with sum of 10, we can progressively record the prefix sum to the node. When we visit A point (denoted by B) whose prefix sum and – destination sum is exactly the same as A previously recorded prefix sum (denoted by A), it means that the sum of the paths going from A to B is exactly the destination sum:

5.3 Free Paths

In this category, the path is no longer required to be from top to bottom, and there are more possibilities. For example, there are altogether 4 paths through node A in the figure below:

So how do we solve these kinds of problems? Remember what we said about recursion? We want to find the optimal solution for this tree, assuming we have the solution for the left and right subtrees, then combine the current nodes to find the final solution. 124. Binary Tree Maximum Path Sum Specifies the Maximum Path Sum of the Binary Tree

In this case, we don’t have to go up and down, and we don’t have to go through the root node, so it’s not optimal. But we can switch and assume that the result goes through the root node and satisfies the optimal substructure: given a tree, suppose we have the maximum sum of the left and right subtrees, then for the current tree, the maximum sum of the two subtrees plus the value of the root node. Of course, the maximum path sum of the root node is not necessarily the maximum path sum of the entire tree, so we need to use a variable to record the maximum recorded.

6. Ancestor issues

6.1 Recent common ancestor

6.2 Furthest common ancestor

  • Related topics in this section:

  • 543. Diameter of Binary Tree

Editting…

5.5 distance

  • All Nodes Distance K in Binary Tree All Nodes Distance K in Binary Tree

7. Special trees

The above trees are all ordinary binary trees. Here are some special binary trees that are common:

7.1 Full binary tree

In a full binary tree, all the leaf nodes are at the bottom, that is, every node except the leaf node has a left node and a right node. For a full binary tree, any subtree is a full binary tree.

– reference time.geekbang.org/column/arti… For the king

7.2 Complete binary tree

In a complete binary tree, the leaves are in the last two layers, and the nodes in the last layer are arranged to the left. For a perfect binary tree, any subtree is a perfect binary tree.

– reference time.geekbang.org/column/arti… For the king

7.3 Binary Search Tree

In a binary search tree, the value of any node is greater than the value of every node in the left subtree, and less than the value of every node in the right subtree. For a binary search tree, any subtree is a binary search tree.

– reference time.geekbang.org/column/arti… For the king

7.4 Balancing binary trees

In a balanced binary tree, the height difference between the left and right subtrees is no more than 1 for any node. For a balanced binary tree, any subtree is a balanced binary tree.

Balanced binary trees avoid the time and space complexity degradation caused by the large difference between the left and right subtrees. However, it should be noted that “approximate balance” is used in practice. It only needs to ensure the relative average height of the left and right subtrees, and it does not need to strictly adhere to the definition of height difference not greater than 1.

– reference time.geekbang.org/column/arti… For the king

7.5 Balanced binary search tree

There are many kinds of balanced binary search trees, such as Splay Tree, Treap and AVL, among which red-black Tree is the most common.

8. Build a binary tree

  • Related questions in this section:

Construct a binary tree by preorder and middle order traversal

Middle order and rear order traversal construct binary tree

Construct a binary tree by traversing the front order

A binary tree is constructed by front-order and back-order traversal

Build the tree with the smallest height

Build a binary search tree

Editting…

9. To summarize

    1. To solve the basic programming skills of tree problem, we must master both recursive and non-recursive writing methods.
    1. The concept of tree is the premise of understanding the meaning of the question, so we must ensure clear understanding and no confusion.
    1. Recursion is very suitable for solving tree problems. When you encounter a problem without a solution, you should first think: if you know the answer to the left and right subtrees (subproblems), can you clearly solve the problem of the current tree;
    1. Tree path & ancestry questions are frequent interview questions.
Tree traversal Hint & problem solving
144. Antecedent traversal of binary trees

Binary Tree Preorder Traversal		 “Antithesis”
Middle order traversal of binary trees

Binary Tree Inorder Traversal		 “Antithesis”
145. Back-order traversal of binary trees

Binary Tree Postorder Traversal		 “Antithesis”
589. Antecedent traversal of N fork trees

N-ary Tree Preorder Traversal		 “Antithesis”
590. Post-order traversal of N fork trees

N-ary Tree Postorder Traversal		 “Antithesis”
404. Sum of left leaves

Sum of Left Leaves		 “Antithesis”
Tree sequence traversal Hint & problem solving
102. Sequence traversal of binary trees

Binary Tree Level Order Traversal		 “Antithesis”
107. Sequential traversal of binary trees (bottom-up)

Binary Tree Level Order Traversal II		 “Antithesis”
103. Sequence traversal of binary trees (sawtooth)

Binary Tree Zigzag Level Order Traversal		 “Antithesis”
429. Sequence traversal of N fork tree

N-ary Tree Level Order Traversal		 “Antithesis”
Find the value in the lower left corner of the tree

Find Bottom Left Tree Value		 “Antithesis”
Tree path traversal Hint & problem solving
257. All paths to a binary tree

Binary Tree Paths		 “Antithesis”
The concept of tree Hint & problem solving
111. Minimum depth of a binary tree

Minimum Depth of Binary Tree		 “Antithesis”
104. Maximum depth of a binary tree

Maximum Depth of Binary Tree		 “Antithesis”
559. Maximum depth of a fork tree

Maximum Depth of N-ary Tree N		 “Antithesis”
662. Maximum Width of Binary Tree
The path of the tree Hint & problem solving
257. All paths to a binary tree

Binary Tree Paths		 “Antithesis”
112. Sum of paths I

Path Sum		 “Antithesis”
129. Sum of numbers from root to leaf

Sum Root to Leaf Numbers		 “Antithesis”
437. Sum of paths III

Path Sum III		 “Antithesis”
1367. Lists in binary trees

Linked List in Binary Tree
572. A subtree of another tree

Subtree of Another Tree
124. The maximum path sum of binary trees

Binary Tree Maximum Path Sum		 “Antithesis”
687. The longest path with the same value

Longest Univalue Path		 “Antithesis”
Ancestors problem Hint & problem solving
236. The most recent common ancestor of binary trees

Lowest Common Ancestor of a Binary Tree		 “Antithesis”
Recent common ancestor of the deepest leaf node

Lowest Common Ancestor of Deepest Leaves		 “Antithesis”
235. The most recent common ancestor of binary search trees

Lowest Common Ancestor of a Binary Search Tree		 “Antithesis”
1483. The KTH ancestor of a tree node

Kth Ancestor of a Tree Node
Maximum difference between a node and its ancestor

Maximum Difference Between Node and Ancestor		 “Antithesis”
Special trees Hint & problem solving
958. Verify complete binary trees

Check Completeness of a Binary Tree
04.04. Verify balanced binary trees

Check Balance LCCI
98. Validate binary search trees

Validate Binary Search Tree

The resources

  • The Beauty of Data Structures and Algorithms. By Wang Zheng. Geek Time
  • Interview with algorithms in 300 Minutes, produced by Liguo & Dragoo.com
  • Summary of BFS Usage Scenarios: Sequence Traversal, Shortest path Problems. By Nettee

Creation is not easy, your “three lian” is chouchou’s biggest motivation, we will see you next time!