查看原文
其他

609,从先序遍历还原二叉树

博哥 数据结构和算法 2022-05-01

问题描述



来源:LeetCode第1028题

难度:困难


我们从二叉树的根节点root开始进行深度优先搜索


在遍历中的每个节点处,我们输出D条短划线(其中D是该节点的深度),然后输出该节点的值。(如果节点的深度为D,则其直接子节点的深度为D+1。根节点的深度为0)。如果节点只有一个子节点,那么保证该子节点为左子节点


给出遍历输出S,还原树并返回其根节点root。


示例 1:

输入:"1-2--3--4-5--6--7"

输出:[1,2,5,3,4,6,7]

示例 2:

输入:"1-2--3---4-5--6---7"

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

示例 3:

输入:"1-401--349---90--88"

输出:[1,401,null,349,88,90]


提示:

  • 原始树中的节点数介于1和1000之间。

  • 每个节点的值介于1和10^9之间。


迭代方式解决



这题输入的是二叉树前序遍历的结果,让我们还原这颗二叉树。如果只给出二叉树的前序遍历结果我们是没法还原的。但这题还给出了两个条件,一个是每个数字前面的“-”表示当前节点的深度,一个是如果一个只有一个子节点,要保证这个子节点是左子节点。那么有了这两个条件,这颗二叉树基本上就能确定了。


我们看一下这题的解题思路:

首先创建一个栈,把创建的节点一个个压入到栈中。你会发现从栈底到栈顶每两个元素之间的关系是父子关系。画个图来看一下

通过上图我们可以发现从栈底到栈顶,1是2的父节点,2是3的父节点。其实还有一个最重要的发现就是栈中元素的个数-1就是栈顶元素的深度。这一个特性非常重要。这里要减1是因为树中节点的深度是从0开始的,不是从1开始,根节点的深度是0。


我们创建每个节点的时候,需要找到他的父节点,然后才能把当前节点挂到他的父节点下面。怎么找呢,就是通过栈中元素的个数来确定。看到这里估计代码大家都已经能写出来了,这里我们先来分开写。


第一步,找出当前节点的深度

//找出当前数字的深度,从0开始的,根节点是第0层
int level = 0;
while (S.charAt(i) == '-') {
    level++;
    i++;
}

第二步,找出当前节点的值

//找出当前节点的值
int val = 0;
while (i < S.length() && S.charAt(i) != '-') {
    val = val * 10 + (S.charAt(i) - '0');
    i++;
}

第三步,找出当前节点的父节点,我们上面分析过,栈中元素的个数-1就栈顶节点的深度。这里一直循环,当栈中元素个数等于level的时候,说明栈顶元素就是当前节点的父节点。

//找到当前节点的父节点,子节点的深度要比父节点大1
while (stack.size() > level) {
    stack.pop();
}

第四步,把当前节点挂到父节点的下面,题中说了如果只有一个子节点,那么这个子节点就是左子节点。这里还要注意的是根节点是没有父节点的。

//创建当前结点
TreeNode node = new TreeNode(val);
//栈为空说明当前节点是根节点,如果栈不为空,说明
//当前节点不是空节点,需要把当前节点挂到他父节点
//的下面
if (!stack.isEmpty()) {
    //如果节点只有一个子节点,那么保证该子节点为左子节点。
    if (stack.peek().left == null) {
        stack.peek().left = node;
    } else {
        //如果左子节点不为空,就放到右子节点中
        stack.peek().right = node;
    }
}
//把当前节点压入栈
stack.add(node);


通过上面我们把代码一步步拆解完之后我们再来看下完整代码。

public TreeNode recoverFromPreorder(String S) {
    Stack<TreeNode> stack = new Stack<>();
    for (int i = 0; i < S.length(); ) {
        //找出当前数字的深度,从0开始的,根节点是第0层
        int level = 0;
        while (S.charAt(i) == '-') {
            level++;
            i++;
        }

        //找出当前节点的值
        int val = 0;
        while (i < S.length() && S.charAt(i) != '-') {
            val = val * 10 + (S.charAt(i) - '0');
            i++;
        }

        //找到当前节点的父节点,子节点的深度要比父节点大1
        while (stack.size() > level) {
            stack.pop();
        }
        //创建当前结点
        TreeNode node = new TreeNode(val);
        //栈为空说明当前节点是根节点,如果栈不为空,说明
        //当前节点不是空节点,需要把当前节点挂到他父节点
        //的下面
        if (!stack.isEmpty()) {
            //如果节点只有一个子节点,那么保证该子节点为左子节点。
            if (stack.peek().left == null) {
                stack.peek().left = node;
            } else {
                //如果左子节点不为空,就放到右子节点中
                stack.peek().right = node;
            }
        }
        //把当前节点压入栈
        stack.add(node);
    }
    //除了根节点,其他子节点全部出栈
    while (stack.size() > 1) {
        stack.pop();
    }
    //返回根节点
    return stack.pop();
}


把字符串拆开



题中说了节点是通过分隔符"-"隔开的,所以我们可以按照"-"把字符串拆开

//通过"-"分隔符把字符串拆开
String[] nodeValues = S.split("-");

这里不需要使用栈,我们可以使用一个list集合存储每层的节点,注意,每层只存储一个节点。我们直接可以通过get方法获取当前节点的父节点,也就是

TreeNode parent = list.get(level - 1);

这里大家可能有点困惑,每层那么多节点我们只存储一个,会不会把之前的给覆盖掉啊,其实会覆盖掉的,但没关系,如果被覆盖掉了,说明覆盖掉的节点以及他的子节点和子子节点……都已经被访问完了。我们不需要再访问了。


比如下面图中红色的节点3在第二层,当遍历到他的时候,就会把第二层的节点2给覆盖掉,覆盖掉了也没关系,因为节点2及他下面的所有子节点都已经被访问完了。

搞懂了上面的分析过程我们再来看下代码

public TreeNode recoverFromPreorder(String S) {
    //通过"-"分隔符把字符串拆开
    String[] nodeValues = S.split("-");
    List<TreeNode> list = new ArrayList<>();
    //数组中的第一个值肯定是根节点,创建根节点然后添加到list中
    list.add(new TreeNode(Integer.valueOf(nodeValues[0])));
    //上面根节点已经加入到list中了,下面都是非根节点
    int level = 1;
    for (int i = 1; i < nodeValues.length; i++) {
        if (!nodeValues[i].isEmpty()) {
            TreeNode node = new TreeNode(Integer.valueOf(nodeValues[i]));
            //因为是前序遍历,每层我们只需要存储一个结点即可,这个节点值有可能
            //会被覆盖,如果被覆盖了说明这个节点以及他的子节点都以及遍历过了,
            //所以我们不用考虑被覆盖问题
            list.add(level, node);
            //获取父节点
            TreeNode parent = list.get(level - 1);
            //左子节点为空,优先添加到左子节点中
            if (parent.left == null) {
                parent.left = node;
            } else {
                parent.right = node;
            }
            //深度要重新赋值
            level = 1;
        } else {
            //统计节点的深度
            level++;
        }
    }
    //返回树的根节点
    return list.get(0);
}


591,二叉树的垂序遍历

582,DFS解二叉树剪枝

580,BFS和DFS解二叉树的堂兄弟节点

564,二叉树最大宽度


截止到目前我已经写了600多道算法题了,为了方便大家阅读,我把部分算法题整理成了pdf文档,目前有1000多页,大家可以在公众号中回复关键字“pdf”即可获取下载链接。

你点的每个赞,我都认真当成了喜欢

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存