Problem: 623. 在二叉树中增加一行

题目描述

思路

1.首先要说明，对于数据结构无非两大类结构：顺序结构、链式结构，而二叉树实质上就可以等效看作为一个二叉链表，而对于链表插入一个节点的操作是应较为熟练掌握的所以二叉树的插入节点操作其实是相类似的操作，同时由于二叉树的特性，我们无法像遍历单链表那样对于二叉树进行迭代遍历操作，而为了实现在二叉树中插入节点，我们有需要利用递归操作完成，具体到本题
2.对于层数为1时，做特殊处理，直接将待插入的节点作为根节点，原始的二叉树作为其左子树
3.对于一般情况，我们做二叉树的先序遍历，当递归到的层数为给定层数减一时进行插入操作即可

复杂度

时间复杂度:

$O(n)$;其中$n$为二叉树的节点个数

空间复杂度:

$O(h)$；其中$h$为二叉树的高度

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int targetVal;
    private int targetDepth;
    private int curDepth = 0;

    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        targetDepth = depth;
        targetVal = val;
        // Insert into the first line with special treatment
        if (targetDepth == 1) {
            TreeNode newRoot = new TreeNode(val);
            newRoot.left = root;
            return newRoot;
        }  
        // Walk through the binary tree and insert the corresponding row
        traverse(root);
        return root;
    }

    private void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        curDepth++;
        if (curDepth == targetDepth - 1) {
            TreeNode newLeftNode = new TreeNode(targetVal);
            TreeNode newRightNode = new TreeNode(targetVal);
            newLeftNode.left = root.left;
            newRightNode.right = root.right;
            root.left = newLeftNode;
            root.right = newRightNode;
        }
        traverse(root.left);
        traverse(root.right);
        curDepth--;
    }
}