[LeetCode] 623. Add One Row to Tree 二叉树中增加一行

Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1.

The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N's left subtree root and right subtree root. And N's original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root's left subtree.

Example 1:

Input: 
A binary tree as following:
       4
     /   \
    2     6
   / \   / 
  3   1 5   

v = 1

d = 2

Output: 
       4
      / \
     1   1
    /     \
   2       6
  / \     / 
 3   1   5   

Example 2:

Input: 
A binary tree as following:
      4
     /   
    2    
   / \   
  3   1    

v = 1

d = 3

Output: 
      4
     /   
    2
   / \    
  1   1
 /     \  
3       1

Note:

1. The given d is in range [1, maximum depth of the given tree + 1].
2. The given binary tree has at least one tree node.

这道题让我们给二叉树增加一行，给了需要增加的值，还有需要增加的位置深度，题目中给的例子也比较能清晰的说明问题。但是漏了一种情况，那就是当 depth=1 时，这该怎么加？这时候就需要替换根结点了。其他情况的处理方法都一样，这里博主第一映像觉得应该用层序遍历来做，每遍历完一层，depth 自减1，当 depth==1 时，需要对于当前层的每一个结点，先用临时变量保存其原有的左右子结点，然后新建值为 val 的左右子结点，将原有的左子结点连到新建的左子结点的左子结点上，将原有的右子结点连到新建的右子结点的右子结点，是不是很绕-.-|||。如果 depth 不为1，那么就是层序遍历原有的排入队列操作，记得当检测到 depth 为0时，直接返回，因为添加操作已经完成，没有必要遍历完剩下的结点，参见代码如下：

解法一：

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        if (!root) return NULL;
        if (depth == 1) {
            TreeNode *newRoot = new TreeNode(val);
            newRoot->left = root;
            return newRoot;
        }
        queue<TreeNode*> q{{root}};
        while (!q.empty()) {
            if (--depth == 0) return root;
            int n = q.size();
            for (int i = 0; i < n; ++i) {
                auto t = q.front(); q.pop();
                if (depth == 1) {
                    TreeNode *left = t->left;
                    TreeNode *right = t->right;
                    t->left = new TreeNode(val);
                    t->right = new TreeNode(val);
                    t->left->left = left;
                    t->right->right = right;
                } else {
                    if (t->left) q.push(t->left);
                    if (t->right) q.push(t->right);
                }
            }
        }
        return root;
    }
};

虽然博主一贯的理念是二叉树问题肯定首选递归来解，但是这道题博主刚开始以为递归没法解，结果看了大神们的帖子，才发现自己还是图样图森破，难道二叉树的问题皆可递归？反正这道题是可以的，而且写法 so 简洁，乍一看上去，会有疑问，题目中明明 depth 的范围是从1开始的，为何要考虑 depth 为0的情况，后来读懂了整个解法后，才为原作者的聪慧叹服。这里 depth 的0和1，其实相当于一种 flag，如果 depth 为1的话，那么将 root 连到新建的结点的左子结点上；反之如果 depth 为0，那么将 root 连到新建的结点的右子结点上，然后返回新建的结点。如果 root 存在且 depth 大于1的话，那么对 root 的左子结点调用递归函数，注意此时若 depth 的值正好为2，那么就不能直接减1，而是根据左右子结点的情况分别赋值1和0，这样才能起到 flag 的作用嘛，叼的飞起，参见代码如下：

解法二：

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        if (depth == 0 || depth == 1) {
            TreeNode *newRoot = new TreeNode(val);
            (depth ? newRoot->left : newRoot->right) = root;
            return newRoot;
        }
        if (root && depth > 1) {
            root->left = addOneRow(root->left, val, depth > 2 ? depth - 1 : 1);
            root->right = addOneRow(root->right, val, depth > 2 ? depth - 1 : 0);
        }
        return root;
    }
};

再来看一种递归的解法，由热心网友 xslin 提供，实际只要根据 depth 的值来分几种情况讨论一下就行了。最开始先对 root 进行判空操作，若为空，则返回空结点。然后判断，若 dpeth 为1，说明是要替换根结点，则新建一个根结点，结点值为 val，左子结点为 root，右子结点为空。否则若 depth 为2，则说明要在根子结点下新加一层，即给 root 新建左右子结点，新建的左子结点的值为 val，其左子结点为 root->left，右子结点为空，同理，新建的右子结点的值为 val，其左子结点为空，右子结点为 root->right。否则若 depth 大于2，则分别对其左右子结点调用递归函数，并使得 depth 自减1即可，参见代码如下：

解法三：

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        if (!root) return NULL;
        if (depth == 1){
            return new TreeNode(val, root, NULL);
        } else if (depth == 2){
            root->left = new TreeNode(val, root->left, NULL);
            root->right = new TreeNode(val, NULL, root->right);
        } else {
            addOneRow(root->left, val, depth - 1);
            addOneRow(root->right, val, depth - 1);
        }
        return root;
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/623

参考资料：

https://leetcode.com/problems/add-one-row-to-tree/

https://leetcode.com/problems/add-one-row-to-tree/discuss/104555/C%2B%2B-Java-10-line-Solution-no-helper

https://leetcode.com/problems/add-one-row-to-tree/discuss/104547/Java-three-methods-one-BFS-and-two-DFS

LeetCode All in One 题目讲解汇总(持续更新中...)