preface

I recently did a little summary of the tree algorithm. These are from Leetcode, and they’re all classic problems that represent the idea of binary tree algorithms.

Such as highly balanced binary tree, binary search tree BST, TIRE tree and other data structures, depth and breadth first traversal, recursion, iteration and other algorithm ideas. If you are not familiar with recursion, you can look at my algorithm in the first article “Oliver Twist”, illustrated and hand edge algorithm, you can also leave a message in the comments, next second Linglong will reply to your brothers and sisters’ questions 😉.

I am also an algorithm scumbag. At the beginning, I could not understand the meaning of recursion when I looked at others’ explanation, just like I did not understand why the car went left before reversing into the garage and steering wheel (covering my face). Anyhow oneself is algorithm idiot 😂. But I think it’s just a matter of time.

The following topic actually I did two to three times to do their own independent solution 😅, share out on the one hand is to give in the algorithm of digging friends some reference, on the one hand is also a summary of their binary tree algorithm (to their May Day gift).

The code is basically javaScript implementation, because the important thing is the idea and the code is not complex, because in the last problem with the knowledge of the prototype chain, so the last problem I also used Java to write a convenient non-front-end digg friend reference. Of course the idea is the same.

Basic concepts of trees

If you are familiar with the structure of the tree in mind then directly look at the problem, open your May Day algorithm journey ~

The concept is introduced

  • Full binary tree: A full binary tree is one in which each node has a left and right subtree and all leaf nodes are on the same level.
  • Complete binary tree: a subset of full binary trees.
  • Balanced binary tree: the height difference between the left and right subtrees of a node is not more than 1
  • Binary search tree: Binary search tree middle order traversal order, left children are smaller than the root, the right children are larger than the root
  • Prefix tree: prefix tree is also called dictionary tree, to a prefix tree picture, from Baidu Encyclopedia

Each node can have 26 different child nodes, and the value of the node is zeroa-zTwenty-six letters.

There are also some basic concepts to understand:

  • Degree of a node: The degree of a node is the number of branches that it shoots out, which is horizontal. The number of branches out is 0 so the degree of the node is 0.
  • Tree degree: The maximum node degree is the tree degree.
  • Tree depth: The maximum node level is the tree depth
  • Node hierarchy: the number of branches from the root node to this node. There is only one node in the number, the node hierarchy is 0

These four concepts are relative, and if they are divided into two categories, they are distinguished from horizontal and vertical. I put it simply: “Live horizontally”. These four words mean the degree of the node so it’s horizontal; The depth of a tree is vertical.

2. Properties of binary trees

Although the following algorithm is rarely used, I think it is a basic literacy to know.

  • Property 1: a nonempty binary tree has at most 2^ I at the i-th level (our I =0 at the first level).
  • Property 2: The number of nodes in a full binary tree is 2^(k+1)-1. K is the 0th layer of node hierarchy. This conclusion can be calculated from a geometric sequence.
  • The leaf node tree of non-empty binary tree is N0, and the node tree of degree 2 is N2, then there exists the relation n0=n2+1. You can tell from the relationship between the branch entry and the branch exit and the conclusion point.

3. Binary tree traversal

A binary tree consists of three parts, the root node, the left subtree, and the right subtree. According to the order of access to the root node, there are three types. Preorder traversal, middle order traversal, and subsequent traversal. In addition to traversal by node type, there is also the same layer traversal by the left subtree and then the right subtree.

  • Pre-order traversal pre-order traversal traverses the root node, then the left subtree, and finally the right subtree.
  • Middle traversal Middle traversal traverses the left subtree, then the root, then the right subtree.
  • Follow-through Follow-through starts at the left subtree, ends at the right subtree, and ends at the root.
  • Ps: Preorder traversal and subsequent traversal cannot identify a tree. We don’t know if the tree is ABnull or AnulB
  • Sequence traversal: Sequence traversal uses queue, fifO idea. Layer by layer. If there are left and right nodes, the left and right nodes are queued, and then the first element is queued. Until the queue is empty. That’s a little abstract, but let’s do it in terms of problems like problem 19.

Non-recursive implementation of traversal

With the help of the stack implementation, the stack has the characteristics of advanced after out. Non-recursive implementation of binary tree pre-order traversal first the root node is pushed, the root node element, if the left subtree is not empty then the left subtree is pushed, then the top of the stack to see if the element has a right node, if the right node is pushed, then the top of the stack until the stack is empty. There will also be related questions like question 12.

Leetcode the original

Basic properties of trees

Problem 1: The maximum height of the tree -104

  • Return the maximum height of a tree, that is, the depth of the tree. As follows:
Given binary tree [3,9,20, NULL, NULL,15,7], 3 / \ 9 20 / \ 15 7 return its depth = 3Copy the code

  • We can find the height of the left subtree and the height of the right subtree. The greater value +1 is the current height of the tree. The height of the left subtree can be solved using the greater value +1 of the height of the left and left subtrees and the height of the right and right subtrees. So we’ve found the recursion pattern. When do we get back? That is, when it’s an exit, it recurses to the last level when the node is empty. So root==null is the exit.

  • The problem solving

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

Problem two — equilibrium tree 110

  • Title: Give you a tree to determine whether it is a balanced binary tree
Given a binary tree, determine if it is height-balanced.
Given the following tree [3,9,20,null,null,15,7]:
    3
   / \
  9  20
    /  \
   15   7
Copy the code

A balanced binary tree is a node whose height difference between the left and right subtrees is <=1

  • Analysis: Similar to the previous, recursively finds the height of the left and right subtrees, and returns false if the height difference between the left and right subtrees is greater than 1, true otherwise. So we need to knowThe height difference between the left and right subtrees of the current node <=1&&The height difference between left and right subtrees of the left child of the current node <=1&&The height difference between the left and right subtrees of the right child of the current node <=1. True if all three conditions are met.
  • The depth function measures the height of the left and right subtrees.
var isBalanced = function(root) {
    if(root==null) return true;
    var cur= Math.abs(depth(root.left)-depth(root.right))>1? false : true;
    return cur&&isBalanced(root.left) && isBalanced(root.right);
}
function depth(root) {
if(root ==null) return 0;
var l = depth(root.left);
var r = depth(root.right);
return Math.max(l,r)+1
}
Copy the code

Problem 3 – Flip tree 226

  • Topic:
Flip a binary tree. Example: Input: 4 / \ 27 / \ / \ 13 6 9 Output: 4 / \ 7 2 / \ / \ 9 6 3 1Copy the code

Force link (LeetCode)

  • Analysis: It can also be implemented recursively, swapping the result of the left subtree flip and the result of the right subtree flip. The flip result of left subtree is the flip result of left left subtree and right right subtree to get… Returns until the left and right subtrees of the last node are empty.
  • Problem solving:
var invertTree = function(root) { if(! root) return null; Root. left = invertTree(root.left); Root. right = invertTree(root.right); var temp = root.left; root.left = root.right; root.right = temp; return root; };Copy the code

Problem 4 – Merge two trees 617

  • Topic:
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: merged Tree: 3 / \ 4 5 / \ 5 4 7Copy the code

Force link (LeetCode)

  • Binary tree merging can be seen as the value of one tree plus the value of another tree. Use recursion. The sum of the current node values + the result of the left subtree merge + the result of the right subtree merge is the last tree to be returned. Result of left subtree merge = value of current node of left child + result of left left subtree merge + result of right right subtree merge. Return until both trees have been traversed.
  • Problem solving:
Var mergeTrees = function(t1, t2) {// If (! t1&&! t2) return null; // If there is an empty if(! t1||! t2) return t1||t2; t1.val = t1.val+t2.val; t1.left = mergeTrees(t1.left, t2.left); t1.right = mergeTrees(t1.right, t2.right); return t1; };Copy the code

Binary tree path problem

Problem 5 – The longest path to the tree 543

  • Topic:
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. Example: Given a binary tree 1 / \ 2 3 / \ 4, 5 returns 3, whose length is the path [4,2,1,3] or [5,2,1,3]. Note: The length of the path between two nodes is expressed as the number of edges between them.Copy the code

Force link (LeetCode)

  • The diameter of a tree is the maximum number of nodes in a tree from one node to another. In their example, it’s easy to think that the maximum length is the height of the left subtree plus the height of the right subtree. However, this is not entirely true. When we traverse each node, we record the maximum diameter of the current node, and then judge the maximum diameter of the next node and the size of the current maximum. If the maximum diameter of the next node is greater than the current maximum, then we need to update the maximum.

For example, in the following example: the diameter of the node with the value -5 is 7, and the diameter of the root node -9 is 6. So the maximum diameter is not necessarily the sum of the depth of the left subtree and the depth of the right subtree


  • The problem solving
var diameterOfBinaryTree = function(root) { if(! root) return 0; var max = 0; function maxdepth(root){ if(! root) return 0; var left = maxdepth(root.left); var right = maxdepth(root.right); Max = math.max ((left+ right), Max); return Math.max(left, right)+1 } maxdepth(root); return max; }Copy the code

The time complexity is O(n): the number of traversal nodes

Space complexity O(height): the height of the tree

Problem 6 – Check whether the sum of paths is equal to the number 112

  • Topic:
Given a binary tree and a destination sum, determine whether there is a path from the root node to the leaf node in the tree. The sum of the values of all nodes along the path equals the destination sum. Note: Leaf nodes are nodes that have no child nodes. Example: Given the following binary tree with the target and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ 7 2 1 returns true because there is a target and a root to leaf path of 22 5->4->11->2.Copy the code

Force link (LeetCode)

  • Parsing: Traverses the tree. Returns true when the sum of all nodes traversed is equal to sum
  • Problem solving:
<! The left subtree will not traverse the right subtree if it does not traverse the right subtree --> <! --var hasPathSum = function(root, sum) {--> <! -- if(! root)return false; -- > <! -- if(root.val == sum&& root.left==null&&root.right==null) return true; -- > <! -- // return hasPathSum(root.left, sum-root.val)||hasPathSum(root.right,sum-root.val); -- > <! -- if(! roo.left)hasPathSum(root.left, sum-root.val); -- > <! -- if(! root.right)hasPathSum(root.right,sum-root.val); -- > <! -}; Var hasPathSum = function(root, sum) {if(! root) return false; if(root.val == sum&& root.left==null&&root.right==null) return true; return hasPathSum(root.left, sum-root.val)||hasPathSum(root.right,sum-root.val); };Copy the code

Question 7 – Counting the number of paths a tree can take

  • Topic:
Given a binary tree, each node contains an integer value. Find paths and the total number of paths equal to the given value. The path does not need to start at the root node or end at the leaf node, but the path direction must be downward (only from parent to child). The number of nodes in the binary tree cannot exceed 1000, and the value of the node is an integer ranging from -1000000 to 1000000. Example: root = [10,5,-3,3,2, NULL,11,3,-2,null,1], sum = 8 10 / \ 5-3 / \ \ 3 2 11 / \ 3-2 1 returns 3. The path where and equals 8 is 1. 5 -> 3 2. 5 -> 2 -> 1 3Copy the code

Force link (LeetCode)

  • The core is also a depth-first tree traversal, but this traversal is different, a path can start at any node, so each node is the root. In the example above, we take 10 as the root and find none. Then we take 5 as the root and find two paths. Then we take 3 as the root to see if there is any…. that meets the requirement

    So how do we know if we’re satisfied? Is the value of the current node equal to sum, and if it’s equal, then we find a set of paths, and then we go through and find all the paths that we want to find starting at the root. This is also a recursion, The recursive equation is the number of paths count= root root value==sum&&root.left Value ==sum-root. value&&root.right Value ==sum-root.left Corresponds to the path function.

  • Problem solving:

Var pathSum = function(root, sum) {if(! root) return 0; function path(root, sum) { var count = 0; if(! root) return 0; if(root && root.val == sum) count++; count += path(root.left, sum-root.val)+path(root.right, sum-root.val); return count; } return path(root, sum)+pathSum(root.left, sum)+pathSum(root.right, sum); };Copy the code

Problem 8 – Minimum path 111

  • The title
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. Note: Leaf nodes are nodes that have no child nodes. Example: Given a binary tree [3,9,20, NULL, NULL,15,7], 3 / \ 9 20 / \ 15 7 returns its minimum depth of 2.Copy the code

Force link (LeetCode)

  • If one of the left and right subtrees is zero, then the value of [1, 2] is not satisfied.
  • Code implementation
var minDepth = function(root) { if(! root) return 0; let l = minDepth(root.left); let r= minDepth(root.right); If (l==0&&r! =0||r==0&&l! =0) return (l||r)+1; return Math.min(l, r)+1; };Copy the code
  • Time complexity: We visit each node once and the time complexity is O(N)O(N), where NN is the number of nodes.
  • Spatial complexity: In the worst case, the whole tree is unbalanced, such as each node has only one child, the recursion is called N times (the height of the tree), so the stack space overhead is O(N). But in the best case, the tree is perfectly balanced with only log(N) height, so the space complexity in this case is only order log(N)).
Method 2

The use of hierarchical traversal and two layers of circulation, not traversal every node. Returns the number of layers of the current node when the current node is a leaf node.

var minDepth = function(root) { if(! root) return 0; if(! root.left&&! root.right) return 1; let quene = []; // queue let level = 0; quene.push(root); while(quene.length){ let size = quene.length while(size--){ let cur = quene.shift(); if(cur.left! =null){ quene.push(cur.left); } if(cur.right! =null) { quene.push(cur.right); } // Find the leaf if(! cur.left&&! cur.right){ return level+1; } } level++; }};Copy the code

9. -124 Calculating the maximum path sum (hard)

  • The title
Given a nonempty binary tree, return its maximum path sum. In this case, a path is defined as a sequence that starts at any node in the tree and reaches any node. The path contains at least one node and does not necessarily go through the root node. Example 1: Input: [1,2,3] 1 / \ 2 3 Output: 6 Example 2: Input: [-10,9,20, NULL,15,7] -10 / \ 9 20 / \ 15 7 Output: 42Copy the code

Force link (LeetCode)

  • The number of nodes in a path is the largest. The number of nodes in a path is the largest. The number of nodes is the largest. Perhaps more seriously, the path sum must not be less than 0, and the tree maximum path sum may be negative (when the value of the node is negative).
  • The problem solving
var maxPathSum = function(root) { let max = Number.MIN_SAFE_INTEGER;; const path = (root) => { if(root == null) return 0; let left = Math.max(0,path(root.left)); let right =Math.max(0,path(root.right)); max = Math.max(max, left+right+root.val); // return left+right+root.val; Return math. Max (left,right)+root.val; } path(root); return max; };Copy the code

Problem 10 – The maximum path length of the same node value is 687

Given a binary tree, find the longest path where each node has the same value. This path may or may not go through the root node. Note: The length of the path between two nodes is represented by the number of edges between them. Example 1: Input: 5 / \ 4 5 / \ 1 1 5 Output: 2 Example 2: Input: 1 / \ 4 5 / \ 4 4 5 Output: 2 Note: the given binary tree has no more than 10000 nodes. The height of the tree does not exceed 1000.Copy the code

Source: LeetCode

  • B) each node is the root of the node. C) each node is the root of the node. Then record the current maximum value and compare and update the maximum value. Leetcode543, leetCode543, leetCode543, leetCode543, leetCode543, leetCode543, LeetCode543, LeetCode543, LeetCode543
  • The problem solving
Var longestUnivaluePath = function(root) {// // Number of paths in the current tree if(! root) return 0; let max = 0; const depth = (root)=>{ if(! root) return 0; let left = depth(root.left); let right = depth(root.right); let leftpath = (root.left&&root.left.val==root.val)? left+1:0; let rightpath = (root.right&&root.right.val==root.val)? right+1:0; max = Math.max(max, leftpath+rightpath); return Math.max(leftpath,rightpath) } depth(root); return max; }; "-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -" a similar path node and there are 129, Var sum = function(root) {let sum = 0; let cur = 0; if(! root) return 0; const path = (root,cur)=>{ cur = cur*10 + root.val; If (root.left) path(root.left, cur); if(root.left) path(root.left, cur); if(root.right) path(root.right, cur); // the sum of leaf nodes is cur if(! root.left&&! root.right) sum += cur; } path(root,0); return sum; };Copy the code

Problem 11. – Subtree 572

  • Title: This is a double recursion similar to the solution to number 7 -437, so I put it here.
Given two nonempty binary trees S and T, test whether S contains subtrees with the same structure and node values as T. A subtree of S consists of a node of S and all the children of that node. S can also be viewed as a subtree of itself. Example 1: Given tree S: 3 / \ 4 5 / \ 1 2 Given tree T: 4 / \ 1 2 returns true because t has the same structure and node values as a subtree of S. Example 2: Given tree S: 3 / \ 4 5 / \ 1 2/0 Given tree T: 4 / \ 1 2 returns false.Copy the code

Force link (LeetCode)

  • A. double recurrence B. double recurrence C. double recurrence D. double recurrence The first level of recursion is to iterate over each node, taking each node of S as the root, and then the second level of recursion is to determine if the two trees are the same. Same is the tree is the same from the root to the leaf. For example, the second example in the problem returns false because the leaves are different.
  • code
var isSubtree = function(s, t) { if(! s) return false; Let judege = function(s, t) {if(! s&&! t) return true; if(! s||! t) return false; if(s.val ! = t.val){ return false; } return judege(s.left,t.left)&&judege(s.right, t.right); } / / as long as a three to return judege (s, t) | | isSubtree (s.l eft, t) | | isSubtree (s.r d.light, t)};Copy the code

Binary tree traversal

12. Non-recursive binary tree traversal 144

  • The title
Given a binary tree, return its prior traversal. Example: Input: [1, NULL,2,3] 1\2/3 Output: [1,2,3] Advanced: The recursive algorithm is simple, can you do it with an iterative algorithm?Copy the code

: LeetCode

  • Parse: preorder traversal, traversal the root, traversal the left subtree, traversal the right subtree. Here we write the iterative algorithm, that is, the use of stack non-recursion to achieve binary tree traversal
  • answer
var preorderTraversal = function(root) { let result = []; if(! root) return result; // const helper = (root) => {// if(root) result.push(root.val); // if(root.left) helper(root.left); // if(root.right) helper(root.right); // } // helper(root); // return result; // Let stack = [root]; while(stack.length! =0){ let node = stack.pop(); result.push(node.val); if(node.right) stack.push(node.right); if(node.left) stack.push(node.left); } return result; };Copy the code

Question 13 – Subsequent Traversal of a nonrecursive Binary tree 145(Hard)

  • The title
Given a binary tree, return an example of its post-order traversal: Input: [1, NULL,2,3] 1\2/3 Output: [3,2,1]Copy the code

Force link (LeetCode)

  • Parsing: Similar to the above method, can be recursively traversed first and then reverse output. Alternatively, you can iterate each time you update the top element of the stack to get the first traversal result and then reverse the output. Note the post-order traversalLeft child, right child, root,. So the order of precedence is thetaRoot node, right child, left childRather thanRoot node, left child, right child
  • code
/** * @param {TreeNode} root * @return {number[]} */ var postorderTraversal = function(root) result = []; if(! root) return result; // const helper = (root) => { // if(root) result.push(root.val); // if(root.right) helper(root.right); // if(root.left) helper(root.left); // } // helper(root); // return result.reverse(); let stack = [root]; while(stack.length){ let len = stack.length; while(len--){ let node = stack.pop(); result.push(node.val) if(node.left) stack.push(node.left); if(node.right) stack.push(node.right); } } return result.reverse(); };Copy the code

Question 14 – Implementing middle Order Traversal of binary trees without Recursion 94(Medium)

  • The title
Given a binary tree, return its middle-order traversal. Example: Input: [1, NULL,2,3] 1\2/3 Output: [1,3,2]Copy the code

Force link (LeetCode)

  • Thought: Although this problem is of medium difficulty, I think the middle order traversal is the most difficult of all three. The left subtree of the root node is pushed through the node pointer, the top element is removed and the node value is saved in the result. If the top element of the stack has a right subtree we push the right subtree in order and then pull the top element. Two of the more difficult points to understand are commented in the code
  • code
var inorderTraversal = function(root) { let result = []; if(! root) return result; let stack = [root]; let node = root.left; // Add node exists to handle the case where the root node has no left subtree. No left subtree stack. The length = 0 when haishu right subtree into the stack to the while (stack. The length | | node) {while (node) {/ / node into the stack stack. Push (node); node = node.left } node = stack.pop(); result.push(node.val); node = node.right; } return result; // if node.right exists, push the left node of the node. };Copy the code

Problem 15 – Symmetry of trees 101

  • The title
Given a binary tree, check whether it is mirror - symmetric. For example, binary trees [1,2,2,3,4,4,3] are symmetric. 1 / \ 2 2 / \ / 3 4 4 3 But the following [1,2,2,null,3,null,3] is not mirror symmetric: 1 / \ 2 2\3 3 progression: can you use both recursion and iteration to solve this problem?Copy the code

Power button (LeetCode

  • If the tree is symmetric, then the left subtree is symmetric with the right subtree, and the right subtree is symmetric with the left subtree.Mirror symmetry = value of the first child of the left subtree is equal to value of the first child of the right subtree + symmetry of left left subtree and right right subtree + symmetry of right right subtree and left left subtree
  • code
// Symmetric = function(root) {if(! root) return true; Let same = function(root1, root2) {let same = function(root1, root2) { root1&&! root2) return true; // Either node is null or the values of the two nodes are not equal. if(! root1||! root2||root1.val ! = root2.val) return false; return same(root1.left,root2.right)&&same(root1.right, root2.left); } return same(root.left,root.right); };Copy the code

Of course, there are iterative methods that use queues, taking the first two elements of a queue at a time and comparing them to see if they are equal. If two nodes are empty for the next loop, false if one or both val are not equal, since the order of the four nodes in the queue must be noticed.

Var isSymmetric = function(root) {// Let quene = []; if(root.left.val! =root.right.val) return false; quene.push(root.left); quene.push(root.right); while(quene.length){ let left = quene.shift(); let right = quene.shift(); // if(left.left! =right.right||left.right! =right.left) return false; Logic error if(! left&&! right) continue; if(! left||! right || left.val ! = right.val) return false; If (left.left) quene.push(left.left); if(right.right) quene.push(right.right); if(left.right) quene.push(left.right); if(right.left) quene.push(right.left); } return true; };Copy the code

Problem 16 – Counting the sum of 404 on the left leaf

  • The title
Computes the sum of all left leaves of a given binary tree. Example: 3 / \ 9 20 / \ 15 7 In this binary tree, there are two left leaves, 9 and 15, so return 24Copy the code

Force link (LeetCode)

  • The recursive implementation returns the value of the left subtree plus the result of processing the right subtree if the left subtree is a leaf. If the left subtree is not a leaf node, the result of processing the left subtree and the right subtree is returned. There are three conditions for judging whether the left subtree is a leaf node: one is that the node exists; the other is that the node has no left child; the third is that the node has no right child.
  • code
var sumOfLeftLeaves = function(root) { if(root==null) return 0; if(root.left&&! root.left.left&&! root.left.right) return root.left.val+sumOfLeftLeaves(root.right); else return sumOfLeftLeaves(root.left)+sumOfLeftLeaves(root.right); };Copy the code

Question 17 – Interval traversal (robbery 2- Good question) 337

  • The title
The clever thief realizes that "the arrangement of all the houses in this place resembles a binary tree". If two directly connected houses are robbed on the same night, the house will automatically alarm the police. Calculate the maximum amount of money a thief could steal in one night without setting off the alarm. Example 1: Input: [3,2,3, NULL,3, NULL,1] 3 / \ 2,3\3 1 Output: 7 Explanation: Maximum amount of money a thief can steal in one night = 3 + 3 + 1 = 7. Example 2: Input: [3,4,5,1,3, NULL,1] 3 / \ 4 5 / \ 1 3 1 Output: 9 Explanation: The maximum amount a thief can steal in one night = 4 + 5 = 9.Copy the code

Force link (LeetCode)

  • Analysis: here the use of recursive method traversal tree, dynamic planning into the dynamic planning column to explain. So this is a problem that you can think of as what is the maximum sum of the values of the nodes between the binary trees. So there are two cases. The first case takes root as the current maximum value, and then root’s left and right cannot be counted. Left +root.left. Left +root.left. Right +root.right. Left +root.right.

    The second case is to exclude root and use the sum of root.left+root.right as the maximum value. The final maximum should be the maximum of the first and the second. The exit for recursion is to return 0 if the node does not exist.

  • Answer:

var rob = function(root) { if(! root) return 0; let result1 =root.val ; If (root.left)result1 += rob(root.left) + rob(root.left); if(root.right) result1 +=rob(root.right.left)+ rob(root.right.right); // let result2 = rob(root.left) + rob(root.right); return Math.max(result1, result2); };Copy the code
  • Add: I didn’t think of this problem at the beginning of the recursion, feeling too awkward, take a break and realize that I have thought of it, traversing the current node to find the maximum of the current two cases, the maximum of the current case is also two cases. Find their maximum. The final result is the result of comparing Result1 with ResulT2. Resul2 resultsresult2 = rob(root.left) + rob(root.right);Rob (root.left) results in root.left as root. Rob (root.right) is the result of root.

Problem 18 – Find 671, the second smallest node in the binary tree

  • The title
Given a nonempty special binary tree, each node is positive and the number of children of each node can only be 2 or 0. If a node has two children, the value of that node is no greater than the value of its children. To give such a binary tree, you need to output the second smallest value of all nodes. If the second smallest value does not exist, print -1. Example 1: Input: 2 / \ 2 5 / \ 5 7 Output: 5 Description: The smallest value is 2 and the second smallest value is 5. Example 2: Input: 2 / \ 22 2 Output: -1 Description: The minimum value is 2, but there is no second smallest value.Copy the code

Force link (LeetCode)

  • The second smallest value must be between the first left child and the first right child of the root node. But we know from the error message that the second smallest value can occur anywhere in the subtree (when the child node has the same value as the root node), so we recurse.
    • The second smallest value cannot be the root node, so the smaller of the left and right subtrees is chosen as the second smallest value
    • Val ==root.val, the second smallest value of the left subtree is found as the value of left. Val =root.val =root.val =root.val
    • And then compare which is bigger, right and left.
  • Wrong ideas
Thoughtless / / wrong idea: part of the test cases pass, such as,1,3,11,34,3,1,1,1,3,8,4,8,3,3,1,2 [1] the tree. // Have 0 or 2 leaves. Var findSecondMinimumValue = function(root) {if(! root) return -1; // Only one root if(! root.left&&! root.right) return -1; // have a leaf node if(! root.left||! root.right) return (root.left.val||root.right.val)> root.val? (root.left.val||root.right.val):-1; If (root.left. Val ==root.val&&root.right. Val ==root.val) return -1; if(root.left.val==root.val) return root.right.val; if(root.right.val == root.val) return root.left.val; return Math.min(root.left.val,root.right.val) };Copy the code
  • The right solution
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; */ /** * @param {TreeNode} root * @return {number} */ / has 0 or 2 leaves. Var findSecondMinimumValue = function(root) {if(! root) return -1; // Only one root if(! root.left&&! root.right) return -1; // let left = root.left. Val; let right = root.right.val; if(left == root.val) left = findSecondMinimumValue(root.left); if(right == root.val) right = findSecondMinimumValue(root.right); // If (left! = -1 && right ! =- 1) return Math.min(left, right); // Only left subtree exists if(left! = -1) return left; // Only the right subtree exists. };Copy the code

Problem 19 – The average of nodes per level of a tree is 637

  • Topic:
Given a non-empty binary tree, return an array of the average values of nodes at each level. Example 1: Input: 3 / \ 9 20 / \ 15 7 Output: [3, 14.5, 11] Explanation: The average of layer 0 is 3, layer 1 is 14.5 and layer 2 is 11. So return [3, 14.5, 11].Copy the code

Force link (LeetCode)

  • Parsing: Sequence traversal, using a queue. The first loop represents the current layer, and the second loop is the node tree of the layer. The nodes of the first layer are queued and taken out to calculate the average value. Then queue the nodes of the second layer and take them out to calculate the average value. Until the queue is empty.
  • answer
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; */ var averageOfLevels = function(root) {let quene = [root]; let result = []; while(quene.length){ let size = quene.length; let sum = 0; let node =null; for(let i = 0; i< size; i++){ node= quene.shift(); sum+=node.val; if(node.left) quene.push(node.left); if(node.right) quene.push(node.right); } result.push(sum/size); } return result; };Copy the code
  • Solution two: DFS traversal implementation: sequential traversal, each traversal record depth, construct a two-dimensional array ARR [I][j], I represents the current depth, J represents the node value of the current depth. Finally, the sum of each reduce method of the two-dimensional array is obtained and the average value is calculated by map method.
var averageOfLevels = function(root) { let arr = []; if(! root) return arr; const Deepfs = (root, level) => { (arr[level]||(arr[level]=[])).push(root.val); if(root.left)Deepfs(root.left, level+1); if(root.right)Deepfs(root.right, level+1); } Deepfs(root, 0); return arr.map(item => { return item.reduce((pre, cur)=> pre+cur)/item.length}); };Copy the code

Problem 20 — get node 513 in the lower left corner

  • The title
Given a binary tree, find the leftmost value in the last row of the tree. Example 1: Input: 2 / \ 1 3 Output: 1Copy the code
  • A. to be b. to be C. be D. to be Use depth-first or breadth-first traversal trees. Breadth-first traversal queues the right subtree and then the left subtree. The last element of the fetch queue is the leftmost child node. The main idea here is to say depth-first traversal, a very clever thinking is that even if the depth of the tree is updated, use result to record the current deepest first node value is the leftmost node value, when the tree traversal is finished, return result
  • code
var findBottomLeftValue = function(root) {
    let maxLevel = -1;
    let result = root.val
     const DFS = (root, level) => {
         if(level>maxLevel) {
             maxLevel = level;
             result = root.val;
         }
         if(root.left) DFS(root.left, level+1);
         if(root.right) DFS(root.right, level+1);
     }
     DFS(root, 0);
     return result;
};
Copy the code

Binary search tree

Problem 21 – Prune binary search tree 669

  • The title
Given a binary search tree, the minimum boundary L and the maximum boundary R are given simultaneously. By pruning the binary search tree, the values of all nodes are in [L, R] (R>=L). You may need to change the root of the tree, so the result should return the new root of the trimmed binary search tree. Example 2: Input: 3 / \ 0 4\2/1 L = 1 R = 3 Output: 3/2/1Copy the code

Force link (LeetCode)

  • What is a binary search number? The size of the root of the binary search number is the intermediate value, that is, the left side of the root is smaller than the root, the right side of the root is larger than the root, and the result of the pruning is equal to the result of the left subtree pruning and the result of the right subtree pruning. The result of the right subtree pruning is the result of the right subtree pruning plus the right and left subtree pruning.
  • code
Var trimBST = function(root, L, R) {if(! root) return null; if(root.val> R){ return trimBST(root.left, L, R); }else 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

Problem 22. Find the KTH element of the binary search tree 230

  • The title
Given a binary search tree, write a function kthSmallest to find the kthSmallest element in the tree. Note: You can assume that k is always valid, 1 ≤ k ≤ the number of binary search tree elements. Example 1: Input: root = [3,1,4, NULL,2], k = 1 3 / \ 1 4\2 Output: 1Copy the code

Force link (LeetCode)

  • The k-1st result of binary search tree is the k-th smallest value of binary search tree.

  • code

var kthSmallest = function(root, k) { let result=[]; if(! root) return ; const helper = (root) => { if(root.left) helper(root.left); result.push(root.val); if(root.right) helper(root.right); } helper(root); return result[k-1]; };Copy the code

Problem 23. – Add the value of each node in the binary search tree to the value of the node greater than 538

  • The title
Given a Binary Search Tree, convert it into a Greater Tree, such that the value of each node is the sum of the original node value plus the sum of all the Greater nodes. For example: input: original Binary Search Tree: 5 / \ 2 13 Output: Convert to an accumulation tree: 18 / \ 20 13Copy the code

Force link (LeetCode)

  • First of all, we must traverse the tree. You want to know the maximum. We can go through in reverse order.Right child, root, left childIs traversed in the order of. The current node value recorded during traversal is represented by sum. The value of the next node, root, is the sum of val and sum.

For example, val of node 8 is 8+0, sum = val =8; And then val of node 7 is 7 plus sum=15, sum=val=15. And then node 4 is the same thing.

  • code
if(! root) return root; let sum = 0; // Const helper = (root)=>{if(! root) return; helper(root.right); root.val+=sum; sum = root.val; helper(root.left); } helper(root); return root };Copy the code

Problem 24 – The nearest common ancestor of a binary search tree 235

  • The title
Given a binary search tree, find the most recent common ancestor of two specified nodes in the tree. For example, given the following binary search tree: root = [6,2,8,0,4,7,9, null, null, 3, 5)Copy the code

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

Force link (LeetCode)

  • You can recurse or iterate. It looks in the left subtree when pq is less than the root, and in the right subtree when pq is greater than the root. The important thing to note here is that p and Q are two nodes, not node values, so use P.val when you compare them.
  • Code (non-recursive iterative methods)
Var lowestCommonAncestor = function(root, p, q) { While (root){if(root.val > q.val && root.val > p.val) root = root.left; else if(root.val < q.val && root.val < p.val) root = root.right; else{ return root; }}};Copy the code

Problem 25 – Constructing a binary lookup tree 108 from an ordered array

  • The title
Converts an ordered array in ascending order into a highly balanced binary search tree. In this case, a highly balanced binary tree means that the absolute value of the height difference between the left and right subtrees of each node of a binary tree is less than 1. Example: Given the ordered array: [-10,-3,0,5,9], a possible answer would be [0,-3,9,-10, NULL,5], which could represent the following highly balanced binary search tree: 0 / \ -3 9 / / -10 5Copy the code

Force link (LeetCode)

  • This problem requires the construction of a highly balanced binary tree, where the middle of an ordered array is the root node. Then divide the array into two halves and construct the highly balanced left binary tree and the highly balanced right subbinary tree respectively. The length of the array is odd and the length of the array is even and the length of the array is either of the middle two.
  • code
var sortedArrayToBST = function(nums) {
    if(nums.length==0) return null;
        const helper = (nums) => {
        if(nums.length==0) return null;
        let len = nums.length;
        let i = Math.floor((len)/2);
        let root = new TreeNode(nums[i]);
        root.left = helper(nums.slice(0, i));
        root.right = helper(nums.slice(i + 1));
        return root;
    }
    return helper(nums);
};
Copy the code

Problem 26 – Constructing a binary search tree from ordered linked lists 109

  • The title
Given a single linked list whose elements are sorted in ascending order, convert it into a highly balanced binary search tree. In this case, a highly balanced binary tree means that the absolute value of the height difference between the left and right subtrees of each node of a binary tree is less than 1. Example: Given an ordered list: [-10, -3, 0, 5, 9], a possible answer would be [0, -3, 9, -10, NULL, 5], which could represent the following highly balanced binary search tree: 0 / \ -3 9 / / -10 5Copy the code

Force link (LeetCode)

  • Idea: Building a binary tree from an ordered list is not as flexible as an ordered array, because lists cannot be quickly located by subscripts like arrays. So we use the fast and slow pointer, the fast pointer moves forward two nodes at a time, and the slow pointer moves forward one node at a time. If the fast pointer is the last node (the list length is odd) and the fast pointer is the second-to-last node (the list length is even), the slow pointer is the middle position. For the left, do the same thing for the middle of the left list, and do the same thing for the middle of the right list.
  • I don’t know if anyone has the same question as me,root.right = helper(slow.next, tail); //tail cannot be written as nullWhy not write tail as null? After all, the tail on the right is null. After analysis, the first list tail to the right of the median is indeed tail, but the first list tail to the left of the median is where slow pointed to. So writing NULL is not correct.
  • code
/** * @param {ListNode} head * @return {TreeNode} */ var sortedListToBST = function(head) { if(! head) return null; const helper = (head, tail)=> { if(head == tail) return null; let fast = head, slow = head; // The list can be even or odd. =tail && fast.next ! = tail){ fast = fast.next.next; slow = slow.next; } let root = new TreeNode(slow.val); root.left = helper(head, slow); root.right = helper(slow.next, tail); //tail cannot be written as null return root; } return helper(head, null); };Copy the code

Problem 27 – Find two nodes in a binary search tree whose sum is a given value of 653

  • The title
Given a binary search tree and a target result, return true if two elements exist in BST and their sum equals the given target result. Case 1: Input: 5 / \ 3 6 / \ 2 4 7 Target = 9 Output: TrueCopy the code

Force link (LeetCode)

  • Parsing: two ideas, the first way to balance the tree node values into an ordered array, and then use fast and slow Pointers. The second idea is to traverse every node of the tree, using a Set to record the value of each node traversed. If the result of k- current node value exists in and Set structure. So there are two nodes like this. Return false if the node has not been traversed.
  • code
var findTarget = function(root, k) { if(! root) return false; let s = new Set(); const helper = (root, k, s) => { if(! root) return false; if(s.has(k-root.val)) return true; s.add(root.val); return helper(root.left, k, s) || helper(root.right, k,s); } return helper(root, k, s) };Copy the code

Problem 28 – Find the minimum absolute value of two nodes in a binary search tree 530

  • The title
You are given a binary search tree in which all nodes are non-negative. Compute the minimum absolute value of the difference between any two nodes in the tree. Example: Input: 1\3/2 Output: 1 Explanation: The minimum absolute difference is 1, where the absolute value of the difference between 2 and 1 is 1 (or 2 and 3).Copy the code

Force link (LeetCode)

  • Analysis: the minimum absolute value difference must appear in the binary search tree sequential traversal arbitrary adjacent nodes. So the binary tree is traversed in order, and the value of the current node minus the value of the previous node as the minimum difference. Walk through each node with the new minimum min.
  • code
var getMinimumDifference = function(root) { // if(! root) return Number.MAX_VALUE; let min = Number.MAX_VALUE; let prenode = null; const helper = (root) => { if(root.left) helper(root.left); if(prenode) min = Math.min(min, root.val - prenode.val); prenode = root; if(root.right) helper(root.right); } helper(root); return min; };Copy the code

Problem 29 – Find the value 501 that occurs most frequently in the binary search tree

  • In a binary search tree, return the node with the most occurrences. Suppose the binary search tree is defined so that the left subtree is less than or equal to the root node and the right subtree is greater than or equal to the root node.
  • The result of a middle-order traversal is ordered. Never to appear,2,2,3,4,2,2,5 [1]A sequence like this, so you go through every node. If the current node val is equal to the previous node val. So it’s going to be count++, if it’s not equal it’s going to be a new value, and let count=1. Compare the size by count and Max. Max is the number of current mode nodes. If count is greater than Max, a new result is found. If they’re equal, they get the same answer. If count is less than Max, go through the next node. Do the same for the next node until the node has been traversed.
  • code
var findMode = function(root) { // 1. In order to iterate over whether the current value compares with the last value. // If count> Max, update the maximum value, empty the result array, and add new data to the result array. // If count= Max, update the current number of new values as before. Add new data directly to result array let prenode = null; let count = 1; let max = 1; let res = []; const helper = (root) => { if(! root) return; helper(root.left); if(prenode) { if(root.val==prenode.val) count++; else count=1; } if(count > max){ max = count; res = []; res.push(root.val); }else if(count == max) res.push(root.val); prenode = root; helper(root.right); } helper(root); return res; };Copy the code

Common ancestor

Remember the common ancestor of binary search tree in question 24? Above we use the iterative way to achieve, here we use recursion to achieve the common ancestor of ordinary binary tree

Problem 30. – The most recent common ancestor of binary trees 236

  • Given a binary tree, find the nearest common ancestor of the two specified nodes in the tree. Leetcode 236 questions
  • Analysis: see if the current node value is equal to the node value of either q or P. If it is equal to then the common ancestor is the current node. If it is not equal to see if there are p and Q in the left and right subtrees, the logic is in the comments of the code, and we know from the question that there is no case where P and Q are not in the binary tree.
  • code
/** * @param {TreeNode} root * @param {TreeNode} p * @param {TreeNode} q * @return {TreeNode} */ var lowestCommonAncestor = function(root, p, q) { if(! root || root.val == p.val || root.val == q.val) return root; let left = lowestCommonAncestor(root.left, p, q); let right = lowestCommonAncestor(root.right, p, q); // Return right if left has no p or q. If left exists and right does not, the left result is returned. If (left == null) return right; else if(right == null) return left; return root; };Copy the code

The prefix tree

Question 31 – A Tire208 (mid)

  • The title
Implement a Trie (prefix tree) with insert, search, and startsWith operations. Example: Trie Trie = new Trie(); trie.insert("apple"); trie.search("apple"); // Return true trie.search("app"); // Return false trie.startswith ("app"); // Return true trie.insert("app"); trie.search("app"); // Return true Note: You can assume that all input is made up of lowercase letters a-z. Ensure that all inputs are non-empty strings.Copy the code

Force link (LeetCode)

  • Analysis: Prefix trees are also called dictionary trees. There are also instructions at the beginning of the article

❝

Also known as word lookup tree, Trie tree, is a tree structure, is a variant of hash tree. It is typically used to count, sort and save large numbers of strings (but not limited to strings), so it is often used for text word frequency statistics by search engine systems. Its advantages are that it reduces query time by using the common prefix of strings, minimizes unnecessary string comparisons, and improves query efficiency over hash trees. —- Baidu Encyclopedia

❞

  • This is probably the most complex of the questions, because there are three functions to write. In fact, the key insert function can be written, so can the following two functions. I will write comments in the code, if there is a place do call me in the comments section.

  • code

  • Js implementation

Next = new Array(26); function trie (val) {this.next = new Array(26); This. isEnd = false; // This. Val = val; }; /** * Inserts a word into the trie. * @param {string} word * @return {void} */ Trie.prototype.insert = function(word) { let len = word.length; // let node = this; for(let i = 0; i< len; I ++) {//word[I] is a string, and charCodeAt converts it to Ascii; let n = word[i].charCodeAt()-97; If (node.next[n] &&) if(node.next[n] &&) if(node.next[n] &&) if(node.next[n] && node.next[n].val==word[i]){ node = node.next[n] }else { node.next[n] = new Trie(word[i]); node= node.next[n]; }} // The last trie isEnd attribute is marked as true, indicating that the last node node.isEnd = true; }; Trie.prototype.search = function(word) { if(! word) return false; let len = word.length; let node = this; let result = true; for(let i = 0; i < len; i++) { let n = word[i].charCodeAt()-97; if(node.next[n]&&node.next[n].val==word[i]) { node = node.next[n]; } else { result = false; break; If (result) result = node.isend; if(result) result = node.isend; return result; }; / / search understand this function also knew the Trie. The prototype. The startsWith = function (prefix) {let len = prefix. Length; let node = this; let result = true; for(let i = 0; i < len; i++) { let n = prefix[i].charCodeAt()-97; if(node.next[n]) { node = node.next[n]; } else { result = false; break; } } return result; };Copy the code
  • Java implementation
Class Trie {// Public char value; Public Trie[] children=new Trie[26]; public Trie[] children=new Trie[26]; Public Boolean endAsWord=false; public Boolean endAsWord=false; public Trie() { } public void insert(String word) { if(word! Char [] charArr= word.tochararray (); Trie currentNode=this; for(int i=0; i<charArr.length; i++){ char currentChar=charArr[i]; Trie node= CurrentNode. children[currentchar-97]; if(node! Value ==currentChar){// Check whether currentNode=node; }else{// create a new leaf node and point to the current leaf node node node=new Trie(); node.value=currentChar; currentNode.children[currentChar-97]=node; currentNode=node; Currentnode.endasword =true; currentNode.endasWord =true; } } public boolean search(String word) { boolean result=true; if(word! =null && ! word.trim().equals("")){ char[] prefixChar=word.toCharArray(); Trie currentNode=this; for(int i=0; i<prefixChar.length; i++){ char currentChar=prefixChar[i]; Trie node=currentNode.children[currentChar-97]; if(node! Value ==currentChar){// Check whether currentNode=node; }else{ result=false; break; } } if(result){ result=currentNode.endAsWord; } } return result; } public boolean startsWith(String prefix) { boolean result=true; if(prefix! =null && ! prefix.trim().equals("")){ char[] prefixChar=prefix.toCharArray(); Trie currentNode=this; for(int i=0; i<prefixChar.length; i++){ char currentChar=prefixChar[i]; Trie node=currentNode.children[currentChar-97]; if(node! Value ==currentChar){// Check whether currentNode=node; }else{ result=false; break; } } } return result; }}Copy the code

Bonus: tail recursion

We all know that recursion is easy to stack overflow, because the number of recursions determines the amount of stack space you have, so if you recurse a lot, you’re easy to stack overflow.

So we have tail recursion. So what is A tail recursion, tail recursion from tail call, end call there is detailed in the ES6 standard introductory book “, that is A function of A tail returns A function of B, B will not use function and the function of internal variable, because it is A function of the final step, the B function when they destroyed the execution of A stack. Since the call location and internal variables are no longer used, you can simply use the call stack of the inner function instead of the outer function.

Here’s an article on tail recursion and time complexity that I think is very well understood

The last

Finally, some personal feelings about algorithms.

The algorithm is really difficult at the beginning, but when you get into it later, you will find that it is very interesting to think about the algorithm, especially when the space complexity and time complexity beat 100%.

At first, I couldn’t understand recursion at all. I had to put my head on the stack, draw pictures and write codes by hand, and write out every step. The result one day passed, sometimes can write dizzy oneself, an is a dregs 🤷♂️

There are two other things I want to say

  • Tree traversal and the five cases, all of the above problems boil down to tree traversal.
  • Write algorithm to be careful, do algorithm to be patient and persistent

If you haven’t practiced the above questions, spend a lot of time practicing them. These questions if they can write out, I think the algorithm behind will be faster and faster drops (big guy please go around 👀👍)

If you don’t understand the topic, please call me in the comments directly. If you don’t clear up the men who accuse me of cheating and playing with women’s feelings, it will be nice

Finally send a late May Day international happy Labor Day, wish you have a full holiday 💕🐱🏍~

This article is formatted using MDNICE

Attached: the way the human brain used to stack for recursion 🤷♀️… ️