Shulou(Shulou.com)06/02 Report--

This article mainly explains "binary tree in JavaScript, dynamic programming and retrospective case analysis". The content of the explanation is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "binary tree, dynamic programming and retrospective case analysis in JavaScript".

Topic description

Given a binary tree, the root node is layer 1 and the depth is 1. Append a row of nodes with a value of v to its layer d.

Add a rule: given a depth value d (positive integer), create two left and right subtrees for N with a value of v for each non-empty node N with a depth of dmur1 layer.

Connect the original left subtree of N to the left subtree of the new node v

Connect the original right subtree of N to the right subtree of the new node v.

If the value of d is 1 and the depth d-1 does not exist, a new root node v is created, and the original entire tree will be the left subtree of v.

Input: A binary tree as following: 4 /\ 2 6 /\ / 3 1 5 v = 1D = 2Output: 4 /\ 1 1 /\ 2 6 /\ / 3 1 5

Basic thought

Preorder traversal of binary tree

The basic structure of the code

Not the final structure, but the general structure.

/ * * @ param {number} cd:current depth, recursive current depth * @ param {number} td:target depth, target depth * / var traversal = function (node, v, cd, td) {/ / recursive to the target depth Create a new node and return if (cd = td) {/ / return new node} / / Recursive if (node.left) {node.left = traversal (node.left, v, cd + 1, td) to the left subtree } / / Recursive if (node.right) {node.right = traversal (node.right, v, cd + 1, td) to the right subtree;} / / returns the old node return node;}; / * Definition for a binary tree node. * function TreeNode (val) {* this.val = val; * this.left = this.right = null; *} * / / * * @ param {TreeNode} root * @ param {number} v * @ param {number} d * @ return {TreeNode} * / var addOneRow = function (root, v, td) {/ / Recursive traversal (root, v, 1, td); return root;} from the root node

Concrete analysis

We can discuss it in categories and deal with it in three cases.

Case 1: target depth the maximum depth of the current recursive path

The reading title found that there is a description: "the range of the entered depth value d is: [1, the maximum depth of the binary tree + 1]"

So, when the target depth happens to be a little deeper than the tree of the current path, the way to deal with it is:

Add val nodes to the left and right branches of the bottom layer node

Case 3: the target depth is 1

Let's analyze the meaning of the question, which says, "if the value of d is 1 and the depth d-1 does not exist, a new root node v is created, and the original whole tree will be the left subtree of v."

This shows that when the target depth is 1, we deal with it in this way.

All codes

/ * * @ param {v} val, insert node with the value * @ param {cd} current depth, recursive current depth * @ param {td} target depth, target depth * @ param {isLeft} determine whether the node of the original target depth is in the left subtree or the right subtree * / var traversal = function (node, v, cd, td, isLeft) {debugger; if (cd = = td) {const newNode = new TreeNode (v) / / if it was originally a left subtree, the target node is still on the left subtree after reset, otherwise if (isLeft) {newNode.left = node;} else {newNode.right = node;} return newNode } / / deal with cases 1 and 2 above if (node.left | | (node.left = null & & cd + 1 = = td) {node.left = traversal (node.left, v, cd + 1, td, true);} if (node.right | (node.right = null & & cd + 1 = = td)) {node.right = traversal (node.right, v, cd + 1, td, false);} return node;} / * Definition for a binary tree node. * function TreeNode (val) {* this.val = val; * this.left = this.right = null *} * / / * @ param {TreeNode} root * @ param {number} v * @ param {number} d * @ return {TreeNode} * / var addOneRow = function (root, v, td) {/ / processing the target depth of 1, which is the third case if (td = 1) {const n = new TreeNode (v); n.left = root; return n;} traversal (root, v, 1, td) Return root;}

Word splitting

Topic description

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, it is determined whether s can be split into one or more words that appear in the dictionary by spaces.

Description:

1. Words in the dictionary can be reused when splitting.

two。 You can assume that there are no repeated words in the dictionary.

Example

Example1 input: s = "applepenapple", wordDict = ["apple", "pen"] output: true explanation: return true because "applepenapple" can be split into "applepenapple". Note: you can reuse the words in the dictionary. Example2 input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] output: false Source: LeetCode Link: https://leetcode-cn.com/problems/word-break

Basic thought

Dynamic programming

Concrete analysis

The key point of dynamic programming is to find the state transition equation.

With this state transfer equation, we can find out the state and results of this stage according to the state and decision results of the previous stage.

Then, the final result can be obtained recursively from the initial value.

In this problem, we use an one-dimensional array to store recursive data for the dynamic programming process.

Suppose the array is dp, and the array elements are true or false

Dp [N] stores whether the substring truncated from 0 to N in the string s is a "splittable" Boolean value.

Let's think about the computing process from a specific intermediate scenario.

Suppose we have

WordDict = ['ab','cd','ef'] s =' abcdef'

And let's assume that we've got the case from Numb1 to Niss5, and now we need to calculate the case of Numb6.

In other words, we have calculated the Boolean value of dp [1] to dp [5], and now we need to calculate dp [6] =?

How do you calculate it?

Now that the new character f has been added to the sequence "abcde", there are six new cases that need to be calculated.

Sequence A + sequence B 1.abcdef + "2.abcde + f3.abcd + ef4.abc + def5.ab + cdef6.a + bcdef Note: when An is detachable and B is detachable, then An is also detachable.

It is not difficult for us to find two points.

1. When An is detachable and B is detachable, then ApatiB is also detachable.

two。 In these six cases, as long as one of the combinatorial sequences is separable, abcdef must be detachable, which leads to dp [6] = true.

The following is the process of dynamically calculating dp [6] based on the existing Boolean values from dp [1] to dp [5]

(note that as long as the calculation is detachable, the break loop can be used.)

Specific code

Var initDp = function (len) {let dp = new Array (len + 1). Fill (false); return dp;}; / * * @ param {string} s * @ param {string []} wordDict * @ return {boolean} * / var wordBreak = function (s, wordDict) {/ / handles the empty string if (s = ='& wordDict.indexOf (') = =-1) {return false;} const len = s.length / / default initial values are all false const dp = initDp (len); const a = s.charAt (0); / / initial values for initializing dynamic programming dp [0] = wordDict.indexOf (a) = =-1? False: true; dp [1] = wordDict.indexOf (a) =-1? False: true; / / i:end / / j:start for (let I = 1; I < len; iTunes +) {for (let j = 0; j = nums.length) {results.push (nums.concat ()); return;} / / initialize I to index for (let I = index; I < nums.length; iTunes +) {/ / index and I exchange? / swap (nums, index, I); recursion (nums, results, index + 1); swap (nums, index, I);}}; / * * @ param {number []} nums * @ return {number [] []} * / var permute = function (nums) {const results = []; recursion (nums, results, 0); return results;} Thank you for your reading, the above is the content of "binary tree in JavaScript, dynamic programming and retrospective case analysis". After the study of this article, I believe you have a deeper understanding of the problem of binary tree, dynamic programming and retrospective case analysis in JavaScript, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.