echo

任生命穿梭 时间的角落

0%

从先序遍历还原二叉树

Posted on Edited on In Valine:

1028. 从先序遍历还原二叉树

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

在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。

如果节点只有一个子节点，那么保证该子节点为左子节点。

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

示例 1：

img

1
2
输入："1-2--3--4-5--6--7"
输出：[1,2,5,3,4,6,7]

示例 2：

img

1
2
输入："1-2--3---4-5--6---7"
输出：[1,2,5,3,null,6,null,4,null,7]

示例 3：

img

1
2
输入："1-401--349---90--88"
输出：[1,401,null,349,88,90]

提示：

  • 原始树中的节点数介于 1 和 1000 之间。
  • 每个节点的值介于 1 和 10 ^ 9 之间。

我们可以依次从字符串 S 中恢复出所有结点，我们每次取出一个结点的值以及它的深度信息：

  • 首先读取若干的 - 字符，直到遇到非 - 字符。通过字符 - 的个数可以得到当前结点的深度信息。
  • 再读取若干数字，直到遇到非数字或字符串结束，得到结点的值。

得到结点的信息之后，需要考虑当前结点需要放在何处。记当前结点为 t ，上一个结点为 s ，实际上只有两种情况：

  1. t 是 s 的左子结点；
  2. t 是根结点到 s 这一条路径上（不包括 s）某一个结点的右子结点。

先序遍历 顺序：”根 – 左 – 右“，结点 s 要在结点 t之前被遍历到，s 可以在 ”根“ 的位置，t 在 ”左“ 的位置； 或者，s 可以在 ”根“ 的位置，t 在 ”右“ 的位置，注意这里 t 并不是 s 的右子结点，而是从树的根结点到结点 s 的路径中一个结点的右子结点，这条路径中不包括结点 s ，因为题目中规定了如果结点只有一个子结点，那么保证该子节点为左子结点。

我们可以使用递归来实现，也可以使用一个栈来模拟递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int index;
    public TreeNode recoverFromPreorder(String S) {
        index = 0;
        return helper(S, 0);
    }

    public TreeNode helper(String S, int depth){
        //字符串遍历完
        if(index > S.length()) return null;
        int curDepth = 0;
        int k = index;
        //计算当前结点的深度
        while(k < S.length() && S.charAt(k) == '-'){
            ++curDepth;
            ++k;
        }
		//当前结点深度与期望深度不符合，为路径中某结点的右子结点，返回空。
        if(curDepth != depth)return null;
        index = k;
        int val = 0;
        //计算结点数值
        while(index < S.length() && Character.isDigit(S.charAt(index))){
            val = val * 10 + (S.charAt(index) - '0');
            ++index;
        }
        //建立结点并递归建立该结点的子节点
        TreeNode node = new TreeNode(val);
        node.left = helper(S, depth + 1);
        node.right = helper(S, depth + 1);
        return node;
    }
}

时间复杂度 O(s)，其中 s 是字符串 S 的长度。

空间复杂度 O(h)，其中 h 是二叉树的高度（递归深度）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode recoverFromPreorder(String S) {
        Deque<TreeNode> path = new LinkedList<>();
        int pos = 0;
        while(pos < S.length()){
            //计算当前结点的深度
            int level = 0;
            while(S.charAt(pos) == '-'){
                ++level;
                ++pos;
            }
            //计算当前结点的值
            int value = 0;
            while(pos < S.length() && Character.isDigit(S.charAt(pos))){
                value = value * 10 + (S.charAt(pos) - '0');
                ++pos;
            }
			//建立结点
            TreeNode node = new TreeNode(value);
            //结点深度和路径长度相等，若路径不为空，当前结点为路径末尾结点的左子节点
            if(level == path.size()){
                if(! path.isEmpty()){
                    path.peek().left = node;
                }
            }else{//结点深度与路径长度不等，结点为路径中某结点的右子结点
                //找到路径中的结点
                while(level != path.size()){
                    path.pop();
                }
                path.peek().right = node;
            }
            //将结点加入路径
            path.push(node);
        }
        //取出栈底元素
        while(path.size() > 1){
            path.pop();
        }
        return path.peek();
    }
}

时间复杂度和空间复杂度同上。