这篇文章主要讲解了“JavaScript中二叉树，动态规划和回溯法案例分析”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“JavaScript中二叉树，动态规划和回溯法案例分析”吧！
题目描述
给定一个二叉树，根节点为第1层，深度为 1。在其第 d 层追加一行值为 v 的节点。
添加规则：给定一个深度值 d （正整数），针对深度为 d-1 层的每一非空节点 N，为 N 创建两个值为 v 的左子树和右子树。
将 N 原先的左子树，连接为新节点 v 的左子树；
将 N 原先的右子树，连接为新节点 v 的右子树。
如果 d 的值为 1，深度 d - 1 不存在，则创建一个新的根节点 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
基本思想
二叉树的先序遍历
代码的基本结构
不是最终结构，而是大体的结构
/** * @param {number} cd:current depth,递归当前深度 * @param {number} td:target depth, 目标深度 */var traversal = function (node, v, cd, td) { // 递归到目标深度，创建新节点并返回 if (cd === td) { // return 新节点 } // 向左子树递归 if (node.left) { node.left = traversal (node.left, v, cd + 1, td); } // 向右子树递归 if (node.right) { node.right = traversal (node.right, v, cd + 1, td); } // 返回旧节点 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) { // 从根节点开始递归 traversal (root, v, 1, td); return root;};具体分析
我们可以分类讨论，分三种情况处理
第1种情况：目标深度<=当前递归路径的最大深度
处理方法：val节点替换该目标深度对应的节点，并且
● 如果目标节点原来是左子树，那么重置后目标节点是val节点的左子树
● 如果目标节点原来是右子树，那么重置后目标节点是val节点的右子树
第2种情况：目标深度>当前递归路径的最大深度
阅读题目发现，有这么一个描述：“输入的深度值 d 的范围是：[1，二叉树最大深度 + 1]”
所以呢，当目标深度恰好比当前路径的树的深度再深一层时，处理方式是：
在最底下那一层节点的左右分支新增val节点
第3种情况：目标深度为1
我们再分析题意，题目里说：“如果 d 的值为 1，深度 d - 1 不存在，则创建一个新的根节点 v，原先的整棵树将作为 v 的左子树。”
这说明当：目标深度为1时，我们的处理方式是这样的
全部代码
/** * @param {v} val,插入节点携带的值 * @param {cd} current depth,递归当前深度 * @param {td} target depth, 目标深度 * @param {isLeft} 判断原目标深度的节点是在左子树还是右子树 */var traversal = function (node, v, cd, td, isLeft) { debugger; if (cd === td) { const newNode = new TreeNode (v); // 如果原来是左子树，重置后目标节点还是在左子树上，否则相反 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;};JavaScript中二叉树,动态规划和回溯法案例分析
