leetcode1028-从先序遍历还原二叉树

彭晨涛 • 2020年6月18日 11:08 • 算法 • 阅读 200

原题

我们从二叉树的根节点 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 之间。

解法

思想

好感动。。我也只能写得出这样的困难题了。

用栈来模拟DFS的过程，并记录当前节点的深度和上一个节点的深度，如果当前节点的深度 = 上一个节点的深度+1，那么说明当前节点是上一个节点的子节点，否则需要将栈中的元素弹出。

代码

class Solution {
    public TreeNode recoverFromPreorder(String S) {
        Stack<TreeNode> stack = new Stack<>();
        int num = 0;
        int prevDepth = -1;
        int depth = 0;
        char[] chars = S.toCharArray();
        TreeNode root = null;
        for(int i = 0;i<chars.length;i++){
            // 是数字
            if(Character.isDigit(chars[i])){
                num = num*10+(chars[i]-'0');
                // 若是一个数字的结尾字符
                if(i==chars.length-1 || !Character.isDigit(chars[i+1])){
                    TreeNode node = new TreeNode(num);
                    // 如果depth为0，记录当前节点为根节点
                    if(depth == 0) root = node;
                    // 如果depth不等于prevDepth+1，说明该节点不是上一个节点的子节点，需要从栈中弹出相应的元素个数
                    if(depth != prevDepth + 1){
                        for(int n = 0;n<prevDepth+1-depth;n++)
                            stack.pop();
                    }
                    // 将该节点添加到上一个节点的子节点
                    if(!stack.isEmpty()){
                        TreeNode prev = stack.peek();
                        if(prev.left == null){
                            prev.left = node;
                        }else prev.right = node;
                    }
                    stack.push(node);
                    num = 0;
                    prevDepth = depth;
                    depth = 0;
                }
            }
            // 是中划线，深度+1
            else depth ++;
        }
        return root;
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode1028-%e4%bb%8e%e5%85%88%e5%ba%8f%e9%81%8d%e5%8e%86%e8%bf%98%e5%8e%9f%e4%ba%8c%e5%8f%89%e6%a0%91/

leetcode1028-从先序遍历还原二叉树

原题

解法

思想

代码

相关推荐

发表回复