Lstmxx的空间

623. 在二叉树中增加一行

给定一个二叉树，根节点为第1层，深度为 1。在其第 d 层追加一行值为 v 的节点。

添加规则：给定一个深度值 d （正整数），针对深度为 d-1 层的每一非空节点 N，为 N 创建两个值为 v 的左子树和右子树。

将 N 原先的左子树，连接为新节点 v 的左子树；将 N 原先的右子树，连接为新节点 v 的右子树。

如果 d 的值为 1，深度 d - 1 不存在，则创建一个新的根节点 v，原先的整棵树将作为 v 的左子树。

链接

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */


function addOneRow(root: TreeNode | null, val: number, depth: number): TreeNode | null {
  if (depth === 1) {
    const r = new TreeNode(val)
    r.left = root
    return r
  }
  if (root === null) {
    return null
  }
  let nodeQues: (TreeNode | null)[] = [root]
  while(nodeQues.length > 0) {
    depth--
    const nodes = nodeQues.splice(0)
    const len = nodes.length
    if (depth === 1) {
      for(let i = 0; i < len; i++) {
        const parent = nodes[i]
        const newLNode = new TreeNode(val)
        if (parent.left) {
          newLNode.left = parent.left
        }
        parent.left = newLNode
        const newRNode = new TreeNode(val)
        if (parent.right) {
          newRNode.right = parent.right
        }
        parent.right = newRNode
      }
      break
    } else {
      nodeQues = nodes.reduce((pre: TreeNode[], n: TreeNode) => {
        n.left && pre.push(n.left)
        n.right && pre.push(n.right)
        return pre
      }, [])
    }
  }
  return root
};