623. 在二叉樹中增加一行 : 簡單二叉樹周遊運用題

題目描述

這是 LeetCode 上的 ​​623. 在二叉樹中增加一行​​ ，難度為 中等。

Tag : 「二叉樹」、「BFS」、「DFS」

給定一個二叉樹的根 ​

​root​

​​ 和兩個整數 ​

​val​

​​ 和 ​

​depth​

​​，在給定的深度 ​

​depth​

​​ 處添加一個值為 ​

​val​

​ 的節點行。

注意，根節點 ​

​root​

​​ 位于深度 

加法規則如下:

• 給定整數​

  ​depth​

  ​​，對于深度為​

  ​depth - 1​

  ​​ 的每個非空樹節點​

  ​cur​

  ​​，建立兩個值為​

  ​val​

  ​​ 的樹節點作為​

  ​cur​

  ​ 的左子樹根和右子樹根。
• ​

  ​cur​

  ​ 原來的左子樹應該是新的左子樹根的左子樹。
• ​

  ​cur​

  ​ 原來的右子樹應該是新的右子樹根的右子樹。
• 如果​

  ​depth == 1​

  ​​ 意味着​

  ​depth - 1​

  ​​ 根本沒有深度，那麼建立一個樹節點，值​

  ​val​

  ​ 作為整個原始樹的新根，而原始樹就是新根的左子樹。

示例 1:

輸入: root = [4,2,6,3,1,5], val = 1, depth = 2

輸出: [4,1,1,2,null,null,6,3,1,5]      

示例 2:

輸入: root = [4,2,null,3,1], val = 1, depth = 3

輸出:  [4,2,null,1,1,3,null,null,1]      

提示:

• 節點數在
• 樹的深度在範圍内

BFS

根據 ​

​BFS​

​​ 來做，每次 ​

​BFS​

​​ 将整一層進行拓展，同時記錄目前深度，當到達第 ​

​depth - 1​

​ 層，則進行加點操作。

Java 代碼：

class Solution {
    public TreeNode addOneRow(TreeNode root, int val, int {
        if (depth == 1) {
            TreeNode ans = new TreeNode(val);
            ans.left = root;
            return ans;
        }
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        int cur = 1;
        while (!d.isEmpty()) {
            int sz = d.size();
            while (sz-- > 0) {
                TreeNode t = d.pollFirst();
                if (cur == depth - 1) {
                    TreeNode a = new TreeNode(val), b = new TreeNode(val);
                    a.left = t.left; b.right = t.right;
                    t.left = a; t.right = b;
                } else {
                    if (t.left != null) d.addLast(t.left);
                    if (t.right != null) d.addLast(t.right);
                }
            }
            cur++;
        }
        return      

TypeScript 代碼：

function addOneRow(root: TreeNode | null, val: number, depth: number): TreeNode | null {
    if (depth == 1) {
        const ans = new TreeNode(val)
        ans.left = root
        return ans
    }
    const stk = new Array<TreeNode>()
    let he = 0, ta = 0, cur = 1
    stk[ta++] = root
    while (he < ta) {
        let sz = ta - he
        while (sz-- > 0) {
            const t = stk[he++]
            if (cur == depth - 1) {
                const a = new TreeNode(val), b = new TreeNode(val)
                a.left = t.left; b.right = t.right
                t.left = a; t.right = b
            } else {
                if (t.left != null) stk[ta++] = t.left
                if (t.right != null) stk[ta++] = t.right
            }
        }
        cur++
    }
    return      

• 時間複雜度：
• 空間複雜度：

DFS

同理，使用 ​

​DFS​

​​ 也可進行求解，在 ​

​DFS​

​ 過程中記錄目前深度。

Java 代碼：

class Solution {
    int d, v;
    public TreeNode addOneRow(TreeNode root, int val, int {
        d = depth; v = val;
        if (d == 1) {
            TreeNode ans = new TreeNode(val);
            ans.left = root;
            return ans;
        }
        dfs(root, 1);
        return root;
    }
    void dfs(TreeNode root, int {
        if (root == null) return ;
        if (cur == d - 1) {
            TreeNode a = new TreeNode(v), b = new TreeNode(v);
            a.left = root.left; b.right = root.right;
            root.left = a; root.right = b;
        } else {
            dfs(root.left, cur + 1);
            dfs(root.right, cur + 1);
        }
    }
}      

TypeScript 代碼：

let d = 0, v = 0
function addOneRow(root: TreeNode | null, val: number, depth: number): TreeNode | null {
    d = depth; v = val
    if (d == 1) {
        const ans = new TreeNode(v)
        ans.left = root
        return ans
    }
    dfs(root, 1)
    return root
};
function dfs(root: TreeNode | null, cur: number): void {
    if (root == null) return
    if (cur == d - 1) {
        const a = new TreeNode(v), b = new TreeNode(v)
        a.left = root.left; b.right = root.right
        root.left = a; root.right = b
    } else {
        dfs(root.left, cur + 1)
        dfs(root.right, cur + 1)
    }
}      

• 時間複雜度：
• 空間複雜度：

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.623​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。