JavaScript中二叉樹，動態(tài)規(guī)劃和回溯法案例分析

這篇文章主要講解了“JavaScript中二叉樹，動態(tài)規(guī)劃和回溯法案例分析”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“JavaScript中二叉樹，動態(tài)規(guī)劃和回溯法案例分析”吧！

題目描述

給定一個二叉樹，根節(jié)點為第1層，深度為 1。在其第 d 層追加一行值為 v 的節(jié)點。

添加規(guī)則：給定一個深度值 d （正整數(shù)），針對深度為 d-1 層的每一非空節(jié)點 N，為 N 創(chuàng)建兩個值為 v 的左子樹和右子樹。

將 N 原先的左子樹，連接為新節(jié)點 v 的左子樹；

將 N 原先的右子樹，連接為新節(jié)點 v 的右子樹。

如果 d 的值為 1，深度 d - 1 不存在，則創(chuàng)建一個新的根節(jié)點 v，原先的整棵樹將作為 v 的左子樹。

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

基本思想

二叉樹的先序遍歷

代碼的基本結(jié)構(gòu)

不是最終結(jié)構(gòu)，而是大體的結(jié)構(gòu)

/** * @param {number} cd:current depth,遞歸當前深度 * @param {number} td:target depth, 目標深度 */var traversal = function (node, v, cd, td) {    // 遞歸到目標深度，創(chuàng)建新節(jié)點并返回  if (cd === td) {    // return 新節(jié)點  }  // 向左子樹遞歸  if (node.left) {    node.left = traversal (node.left, v, cd + 1, td);  }  // 向右子樹遞歸  if (node.right) {    node.right = traversal (node.right, v, cd + 1, td);  }  // 返回舊節(jié)點  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) {    // 從根節(jié)點開始遞歸  traversal (root, v, 1, td);  return root;};

具體分析

我們可以分類討論，分三種情況處理

第1種情況：目標深度<=當前遞歸路徑的最大深度

處理方法：val節(jié)點替換該目標深度對應(yīng)的節(jié)點，并且

● 如果目標節(jié)點原來是左子樹，那么重置后目標節(jié)點是val節(jié)點的左子樹

● 如果目標節(jié)點原來是右子樹，那么重置后目標節(jié)點是val節(jié)點的右子樹

第2種情況：目標深度>當前遞歸路徑的最大深度

閱讀題目發(fā)現(xiàn)，有這么一個描述：“輸入的深度值 d 的范圍是：[1，二叉樹最大深度 + 1]”

所以呢，當目標深度恰好比當前路徑的樹的深度再深一層時，處理方式是：

在最底下那一層節(jié)點的左右分支新增val節(jié)點

第3種情況：目標深度為1

我們再分析題意，題目里說：“如果 d 的值為 1，深度 d - 1 不存在，則創(chuàng)建一個新的根節(jié)點 v，原先的整棵樹將作為 v 的左子樹?！?/p>

這說明當：目標深度為1時，我們的處理方式是這樣的

全部代碼

/** * @param {v} val,插入節(jié)點攜帶的值 * @param {cd} current depth,遞歸當前深度 * @param {td} target depth, 目標深度 * @param {isLeft}  判斷原目標深度的節(jié)點是在左子樹還是右子樹 */var traversal = function (node, v, cd, td, isLeft) {  debugger;  if (cd === td) {    const newNode = new TreeNode (v);    // 如果原來是左子樹，重置后目標節(jié)點還是在左子樹上，否則相反    if (isLeft) {      newNode.left = node;    } else {      newNode.right = node;    }    return newNode;  }  // 處理上述的第1和第2種情況  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) {  // 處理目標深度為1的情況，也就是上述的第3種情況  if (td === 1) {    const n = new TreeNode (v);    n.left = root;    return n;  }  traversal (root, v, 1, td);  return root;};

單詞拆分

題目描述

給定一個非空字符串 s 和一個包含非空單詞列表的字典 wordDict，判定 s 是否可以被空格拆分為一個或多個在字典中出現(xiàn)的單詞。

說明：

1.拆分時可以重復(fù)使用字典中的單詞。

2.你可以假設(shè)字典中沒有重復(fù)的單詞。

Example

example1輸入: s = "applepenapple", wordDict = ["apple", "pen"]輸出: true解釋: 返回 true 因為 "applepenapple" 可以被拆分成 "apple pen apple"。注意: 你可以重復(fù)使用字典中的單詞。example2輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]輸出: false來源：力扣（LeetCode）鏈接：https://leetcode-cn.com/problems/word-break

基本思想

動態(tài)規(guī)劃

具體分析

動態(tài)規(guī)劃的關(guān)鍵點是：尋找狀態(tài)轉(zhuǎn)移方程

有了這個狀態(tài)轉(zhuǎn)移方程，我們就可以根據(jù)上一階段狀態(tài)和決策結(jié)果，去求出本階段的狀態(tài)和結(jié)果

然后，就可以從初始值，不斷遞推求出最終結(jié)果。

在這個問題里，我們使用一個一維數(shù)組來存放動態(tài)規(guī)劃過程的遞推數(shù)據(jù)

假設(shè)這個數(shù)組為dp，數(shù)組元素都為true或者false,

dp[N] 存放的是字符串s中從0到N截取的子串是否是“可拆分”的布爾值

讓我們從一個具體的中間場景出發(fā)來思考計算過程

假設(shè)我們有

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

并且假設(shè)目前我們已經(jīng)得出了N=1到N=5的情況，而現(xiàn)在需要計算N=6的情況

或者說，我們已經(jīng)求出了dp[1] 到dp[5]的布爾值，現(xiàn)在需要計算dp[6] = ?

該怎么計算呢？

現(xiàn)在新的字符f被加入到序列“abcde”的后面，如此以來，就新增了以下幾種6種需要計算的情況

A序列 + B序列1.abcdef + ""2.abcde + f3.abcd + ef4.abc + def5.ab + cdef6.a + bcdef注意：當A可拆且B可拆時，則A+B也是可拆分的

從中我們不難發(fā)現(xiàn)兩點

1. 當A可拆且B可拆時，則A+B也是可拆分的

2. 這6種情況只要有一種組合序列是可拆分的，abcdef就一定是可拆的，也就得出dp[6] = true了

下面是根據(jù)根據(jù)已有的dp[1] 到dp[5]的布爾值，動態(tài)計算dp[6] 的過程

（注意只要計算到可拆，就可以break循環(huán)了）

具體代碼

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) {  // 處理空字符串  if (s === '' && wordDict.indexOf ('') === -1) {    return false;  }  const len = s.length;  // 默認初始值全部為false  const dp = initDp (len);  const a = s.charAt (0);  // 初始化動態(tài)規(guī)劃的初始值  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; i++) {    for (let j = 0; j <= i; j++) {      // 序列[0,i] = 序列[0,j] + 序列[j,i]      // preCanBreak表示序列[0,j]是否是可拆分的      const preCanBreak = dp[j];      // 截取序列[j,i]      const str = s.slice (j, i + 1);      // curCanBreak表示序列[j,i]是否是可拆分的      const curCanBreak = wordDict.indexOf (str) !== -1;      // 情況1: 序列[0,j]和序列[j,i]都可拆分，那么序列[0,i]肯定也是可拆分的      const flag1 = preCanBreak && curCanBreak;      // 情況2: 序列[0,i]本身就存在于字典中，所以是可拆分的      const flag2 = curCanBreak && j === 0;      if (flag1 || flag2) {        // 設(shè)置bool值，本輪計算結(jié)束        dp[i + 1] = true;        break;      }    }  }  // 返回最后結(jié)果  return dp[len];};

全排列

題目描述

給定一個沒有重復(fù)數(shù)字的序列，返回其所有可能的全排列。

Example

輸入: [1,2,3]輸出:[  [1,2,3],  [1,3,2],  [2,1,3],  [2,3,1],  [3,1,2],  [3,2,1]]

基本思想

回溯法

具體分析

1. 深度優(yōu)先搜索搞一波，index在遞歸中向前推進

2. 當index等于數(shù)組長度的時候，結(jié)束遞歸，收集到results中（數(shù)組記得要深拷貝哦）

3. 兩次數(shù)字交換的運用，計算出兩種情況

具體代碼

var swap = function (nums, i, j) {  const temp = nums[i];  nums[i] = nums[j];  nums[j] = temp;};var recursion = function (nums, results, index) {  // 剪枝  if (index >= nums.length) {    results.push (nums.concat ());    return;  }  // 初始化i為index  for (let i = index; i < nums.length; i++) {    // index 和 i交換？？    // 統(tǒng)計交換和沒交換的兩種情況    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;};

感謝各位的閱讀，以上就是“JavaScript中二叉樹，動態(tài)規(guī)劃和回溯法案例分析”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對JavaScript中二叉樹，動態(tài)規(guī)劃和回溯法案例分析這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！