聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

加一行!

2021-07-19 19:54 浏览: 3801226 次 我要评论(0 条) 字号:

来自公众号:袁厨的算法小屋

今天看到一道有趣的题目,分享给大家。

题目不难,但是我感觉挺有意思,大家可以看一下。

做该题之前,我们先来复习下二叉树的基础知识,重点关注节点的层数和深度之间的关系

更多基础知识大家可以看这篇文章,一文读懂二叉树

话不多说,咱们直接看题。

leetcode 623在二叉树中增加一行

题目很容易理解,让我们在二叉树特定的层数添加一层特定的节点。见下图

有点丑见谅

大家有没有发现添加前和添加后,有什么不同?是不是多了一层节点,然后还变丑了?尽力了哈哈,还是画的不帅。

题目已经搞懂,那么大家看到这个题目的第一想法是什么呢?

我的想法是直接进行层序遍历,然后找到对应的层,直接添加新节点即可,和向链表中添加节点的含义类似。

大家如果忘记了层序遍历,可以去这个文章进行复习,这里对可以使用层序遍历的题目进行了总结。

揉碎二叉树

好啦既然我们已经有了做题思路,那么咱们直接直接将思路模拟出来吧!

我们使用这棵树来举例

向这棵树的第 3 层插入,值为 0 的节点。



上面的动画中,为了表述清晰,所以将添加节点的步骤进行了省略,直接进行添加,具体步骤如下。

插入新节点步骤

好啦,到这里我们这个题目就解决啦,下面我们直接看代码吧,当然我这里只是一种写法,大家可以随意发挥。

BFS代码

class Solution {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        
        int level = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        if (depth == 1) {
            TreeNode test = new TreeNode(val);
            test.left = root;
            return test;
        }
        queue.add(root);
        while (!queue.isEmpty()) {
            level++;
            int size = queue.size();
            for (int i = 0 ; i < size; ++i) {
                TreeNode temp = queue.poll();
                if (level == depth - 1) {
                  TreeNode node1 = new TreeNode(val);
                  TreeNode node2 = new TreeNode(val);
                  node1.left = temp.left;
                  node2.right = temp.right;
                  temp.left = node1;
                  temp.right = node2;
                } else {
                     if (temp.left != null) queue.offer(temp.left);             
                     if (temp.right != null) queue.offer(temp.right);
                }                          
            }
            if (depth - 1 == level) break;          
        }
        return root;
    }
}

时间复杂度O(n)空间复杂度O(n)

当然这个题目也可以使用 dfs 解决,具体思路如下。是个很简单的深度优先搜索,当达到指定层数的某节点时,为其添加节点即可。

那我们来想一下结束递归的条件,当root == null 时,我们直接 return当我们搜索到待插入的那一层时,我们直接插入节点即可,否则的则继续进行搜索,代码很简单,比仅仅比二叉树的 dfs 多了一丢丢逻辑。

其实你搞定上面的那个方法,这个也很快就能想到嘞,那么我们直接看代码吧。

DFS代码

class Solution {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            TreeNode temp = new TreeNode(val);
            temp.left = root;
            return temp;
        }
        dfs(root,val,depth,1);
        return root;
    }
    public void dfs(TreeNode root, int val, int depth, int level) {
        if (root == null) {
            return;
        }
        if (level  == depth - 1) {
             TreeNode node1 = new TreeNode(val);
             TreeNode node2 = new TreeNode(val);
             node1.left = root.left;
             node2.right = root.right;
             root.left = node1;
             root.right = node2;
        } else {
            dfs(root.left, val, depth, level+1);
            dfs(root.right, val, depth, level+1);
        }
    }
}

时间复杂度O(n),空间复杂度O(n)。


--- EOF ---


推荐↓↓↓


网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复