刷题leetcode623 Add One Row to Tree

阳光穿透心脏的1/2处 2021-10-09 03:44 238阅读 0赞

2018.1.7 10:42am

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.

题目意思：给第d行插入节点值为v,原来的树的结构放在新插入的节点的后面（左右子树不变）

知识点：二叉树，插入，root.left, root.right，二叉树问题用 **递归**方法做。

思路：分3种情况：

（1）插入到根节点位置：d=1

（2）插入到第二行：d=2

（3）插入到第二行之后：递归，每次分解成更小的树，即每次迭代为原树的left或right子树，那么插入的层数就也减小一层（d->d-1，只是数值上相对减小一），直到插入的层数减小到2,1 时会递归回来了，

解决方法：

![SouthEast][]

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode addOneRow(TreeNode root, int v, int d) {
            if(root == null)
                return null;
            //如果插到根节点位置
            if(d==1){
                TreeNode newleft=new TreeNode(v);
                newleft.left = root;        
                root = newleft;
            }else if(d==2){  //如果插入到根节点下面，即第二行
                 TreeNode newleft = new TreeNode(v);
                 TreeNode newright = new TreeNode(v);
                 newleft.left = root.left;
                 newright.right = root.right;
                 root.left = newleft;
                 root.right = newright;
                 
            }else{  //如果插入到第二行之后
                //递归，缩小范围（取子树root.left,root.right），相当于插入的深度减少一层(d-1)
                addOneRow(root.left,v,d-1);
                addOneRow(root.right,v,d-1);
                
            }
            return root;
            
        }
    }

方法二:利用堆栈进行插入

参考： [leetcode解析][leetcode]  https://leetcode.com/articles/add-one-row-in-a-tree/

思路： 创建类Node(两个属性： node和depth是深度 ) 先把根节点压入堆栈，遍历堆栈，从堆栈弹出根结点判断一下，如果该结点的深度为d-1,即可以把新节点查到这个节点的下面，剩余的其他结点就直接接上去，结束。

如果深度不是d-1,就把根节点的左右子结点压入，和深度depth+1。循环的过程先弹出判断是不是等于d-1,如果是，就插入新节点，如果不是就再把它的子节点放到堆栈里面，（每次都是先弹出，判断是否等于d-1, 不等于的情况下再把子节点压入，下一轮循环再弹出。保证堆栈最多有2个对象。不是一直压入）所以当堆栈为空的时候就结束了。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        class Node{
            Node(TreeNode n,int d){
                node=n;
                depth=d;
            }
            TreeNode node;
            int depth;
        }
        public TreeNode addOneRow(TreeNode t, int v, int d) {
            if (d == 1) {
                TreeNode n = new TreeNode(v);
                n.left = t;
                return n;
            } 
            Stack<Node> stack=new Stack<>();
            stack.push(new Node(t,1));
            while(!stack.isEmpty())
            {
                Node n=stack.pop();
                if(n.node==null)
                    continue;
                if (n.depth == d - 1 ) {
                    TreeNode temp = n.node.left;
                    n.node.left = new TreeNode(v);
                    n.node.left.left = temp;
                    temp = n.node.right;
                    n.node.right = new TreeNode(v);
                    n.node.right.right = temp;
                    
                } else{
                    stack.push(new Node(n.node.left, n.depth + 1));
                    stack.push(new Node(n.node.right, n.depth + 1));
                }
            }
            return t;
        }
    }

[SouthEast]: /images/20211009/eaa4e2fa3df94b978e506e30e483a4b3.png
[leetcode]: https://leetcode.com/articles/add-one-row-in-a-tree/