讨论/《深度优先搜索》 - 练习:从先序遍历还原二叉树/
《深度优先搜索》 - 练习:从先序遍历还原二叉树
共 5 个回复

正则太慢了,换了个效率高一点的,参照的是 android LayoutInflater 里的算法,比正则快了三十几倍

class Solution {

    public TreeNode recoverFromPreorder(String S) {
        TreeNode dummy = new TreeNode();
        recoverFromPreorder(dummy, S, -1, 0);
        return dummy.left;
    }

    // parent 为父节点,S 为原始字符串,depth 为父节点的深度,index 为 S 子串的起始位置
    public int recoverFromPreorder(TreeNode parent, String S, int depth, int index) {
        if (index >= S.length()) {
            return index;
        }
        // 循环里的逻辑是添加子节点
        while (index < S.length()) {
            int currentDepth = getDepth(S, index);
            // 当前节点的深度小于或等于 parent 节点的深度,那么退出循环,这个子节点肯定不应该挂到 parent 下面
            if (currentDepth <= depth) {
                break;
            }
            // 获取节点值
            int end = (index += currentDepth);
            while (end < S.length() && S.charAt(end) != '-') {
                 end++;
            }
            int number = Integer.parseInt(S.substring(index, end));
            index = end; // 更新索引
            // 将当前节点挂到 parent 上
            TreeNode tree = new TreeNode();
            tree.val = number;
            if (parent.left == null) {
                parent.left = tree;
            } else {
                parent.right = tree;
            }
            // 继续遍历后续节点,完成 tree 的构造
            index = recoverFromPreorder(tree, S, currentDepth, index);
        }
        // parent 构造完毕,返回未遍历的子串的索引
        return index;
    }
 
    // 获取当前节点的深度,比如 --2---3----2 返回 2,-9--999 则放回 1
    public int getDepth(String S, int start) {
        int index = 0;
        while (start + index < S.length() && S.charAt(start + index) == '-') {
            index++;
        }
        return index;
    }
}

这其实是个考察正则表达式的题目?

class Solution {

    public TreeNode recoverFromPreorder(String S) {
        return recoverFromPreorder(S, 0);
    }

    public TreeNode recoverFromPreorder(String S, int depth) {
        if (S.length() == 0) {
            return null;
        }
        String[] result = S.split("(?<!-)-{" + (depth + 1) + "}(?!-)");
        TreeNode tree = new TreeNode();
        if (result.length >= 1) {
            tree.val = Integer.valueOf(result[0]);
        } else {
            return null;
        }

        if (result.length >= 2) {
            tree.left = recoverFromPreorder(result[1], depth + 1);
        }

        if (result.length >= 3) {
            tree.right = recoverFromPreorder(result[2], depth + 1);
        }
        return tree;
    }
}
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        if not S: return None
        # 维护一个栈,储存节点和节点对应的level,模拟深度优先搜索
        stack, pos, n = [], 0, len(S)
        # 遍历 S
        while pos < n:
            # 根据 - 的个数,计算level
            level = 0
            while S[pos] == "-":
                level += 1
                pos += 1
            # 计算连续非 - 的值来计算节点值,避免最后一个数字导致pos越界    
            value = 0
            while pos < n and S[pos] != "-":
                value = 10 * value + int(S[pos])
                pos += 1
            # 生成当前节点
            node = TreeNode(value)
            #  level = 0 的最小节点,也就是根节点
            if not stack:
                stack.append((node, level))
            else:
                # level大于栈顶节点的level,则当前节点为栈顶节点的左孩子
                # level等于栈顶节点的level,则当前节点为栈顶节点的兄弟节点,需要出栈,找到父节点
                # level小于栈顶节点,则需要一直出栈,找到当前level的同级节点或父节点
                pre_node, pre_level = stack[-1]
                # 循环出栈,找同级节点或父节点
                while level < pre_level:
                    stack.pop()
                    pre_node, pre_level = stack[-1]
                # 第一个大于栈顶level的节点为左节点
                if level > pre_level:
                    pre_node.left = node
                # 同级节点,需出栈,找到父节点,此节点为父节点的右节点
                else:
                    stack.pop()
                    pre_node, pre_level = stack[-1]
                    pre_node.right = node
                stack.append((node, level))
        # 根节点的level大于所有其他节点的level,不会出栈
        return stack[0][0]

Definition for a binary tree node.

class TreeNode:

def init(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

class Solution:
def init(self):
self.idx = 0
def recoverFromPreorder(self, S: str) -> TreeNode:
# "1-401--349---90--88"
lens = len(S)
def dfs(depth):
cur = 0
# 如果不是数字计算当前的深度
while self.idx < lens and S[self.idx] == "-":
cur += 1
self.idx += 1
# 如果当前的深度和depth不同
if cur != depth:
self.idx -= cur
return None
# 如果是数字,求出整个数字
cur_num = 0
while self.idx < lens and S[self.idx] != "-":
cur_num = cur_num*10 + int(S[self.idx])
self.idx += 1
# 创建当前节点的值
root = TreeNode(cur_num)
# 先考虑左节点
root.left = dfs(depth + 1)
# 右节点
root.right = dfs(depth + 1)
return root
return dfs(0)

class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        ans = {-1: TreeNode(0)}
        def add_tree(v, p):
            ans[p] = TreeNode(int(''.join(v)))
            if not ans[p-1].left:
                ans[p-1].left = ans[p]
            else:
                ans[p-1].right = ans[p]
        ns = list(S+'-')
        i = isDigtal = dep = 0
        for j,c in enumerate(ns):
            if c == '-':
                if isDigtal:
                    add_tree(ns[i:j],dep)
                    dep = 1
                    i = j
                else: dep += 1
                isDigtal = 0
            else:
                if not isDigtal: i = j
                isDigtal = 1
        return ans[0]