golang 解法, 执行用时: 0 ms, 内存消耗: 4.4 MB, 提交时间: 2023-04-13 09:25:18

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func recoverFromPreorder(traversal string) *TreeNode {
    path, pos := []*TreeNode{}, 0
    for pos < len(traversal) {
        level := 0
        for traversal[pos] == '-' {
            level++
            pos++
        }
        value := 0
        for ; pos < len(traversal) && traversal[pos] >= '0' && traversal[pos] <= '9'; pos++ {
            value = value * 10 + int(traversal[pos] - '0')
        }
        node := &TreeNode{Val: value}
        if level == len(path) {
            if len(path) > 0 { path[len(path)-1].Left = node }
        } else {
            path = path[:level]
            path[len(path)-1].Right = node
        }
        path = append(path, node)
    }
    return path[0]
}

python3 解法, 执行用时: 76 ms, 内存消耗: 15.6 MB, 提交时间: 2023-04-13 09:25:03

# 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 recoverFromPreorder(self, traversal: str) -> TreeNode:
        path, pos = list(), 0
        while pos < len(traversal):
            level = 0
            while traversal[pos] == '-':
                level += 1
                pos += 1
            value = 0
            while pos < len(traversal) and traversal[pos].isdigit():
                value = value * 10 + (ord(traversal[pos]) - ord('0'))
                pos += 1
            node = TreeNode(value)
            if level == len(path):
                if path:
                    path[-1].left = node
            else:
                path = path[:level]
                path[-1].right = node
            path.append(node)
        return path[0]

java 解法, 执行用时: 5 ms, 内存消耗: 42 MB, 提交时间: 2023-04-13 09:24:44

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode recoverFromPreorder(String traversal) {
        Deque<TreeNode> path = new LinkedList<TreeNode>();
        int pos = 0;
        while (pos < traversal.length()) {
            int level = 0;
            while (traversal.charAt(pos) == '-') {
                ++level;
                ++pos;
            }
            int value = 0;
            while (pos < traversal.length() && Character.isDigit(traversal.charAt(pos))) {
                value = value * 10 + (traversal.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();
    }
}

cpp 解法, 执行用时: 16 ms, 内存消耗: 19 MB, 提交时间: 2023-04-13 09:24:24

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* recoverFromPreorder(string traversal) {
        stack<TreeNode*> path;
        int pos = 0;
        while (pos < traversal.size()) {
            int level = 0;
            while (traversal[pos] == '-') {
                ++level;
                ++pos;
            }
            int value = 0;
            while (pos < traversal.size() && isdigit(traversal[pos])) {
                value = value * 10 + (traversal[pos] - '0');
                ++pos;
            }
            TreeNode* node = new TreeNode(value);
            if (level == path.size()) {
                if (!path.empty()) {
                    path.top()->left = node;
                }
            }
            else {
                while (level != path.size()) {
                    path.pop();
                }
                path.top()->right = node;
            }
            path.push(node);
        }
        while (path.size() > 1) {
            path.pop();
        }
        return path.top();
    }
};

javascript 解法, 执行用时: 88 ms, 内存消耗: 46.2 MB, 提交时间: 2023-04-13 09:23:58

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {string} S
 * @return {TreeNode}
 */
var recoverFromPreorder = (S) => {
  let index = 0   // 遍历字符串的指针

  const buildTree = (S, level) => { // 构建当前子树，它属于第level层
    let curLevel = 0                // 当前遇到的节点的level
    while (index < S.length && S[index] == '-') {
      curLevel++  // 计算curNode的level
      index++     // 指针步进，+1
    }
    if (curLevel < level) { // 我们想要构建第level层的一个子树，但遇到的当前节点的curLevel
                           // 却不等于level(比level小)，说明该子树已经构建完毕，要出递归栈（结束递归）
      index -= curLevel // 刚刚的while循环，index已经前进了curLevel长度，要退回来
      return null       // 递归的出口，返回null节点
    }
    let start = index   // 记录节点值开头的位置
    while (index < S.length && S[index] != '-') {
      index++           // 指针随着节点值推进
    }
    let val = S.slice(start, index) // 截取出节点值
    let curNode = new TreeNode(val) // 创建当前节点
    curNode.left = buildTree(S, level + 1)  // 构建当前节点的左子树
    curNode.right = buildTree(S, level + 1) // 构建当前节点的右子树
    return curNode // 返回子树
  }

  return buildTree(S, 0) // 构建第0层的子树，即整个树
};

javascript 解法, 执行用时: 80 ms, 内存消耗: 46.5 MB, 提交时间: 2023-04-13 09:23:33

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {string} s
 * @return {TreeNode}
 */
var recoverFromPreorder = (s) => {
    const stack = []; // 维护一个栈
    for (let i = 0; i < s.length; ) {
        let curLevel = 0; // 当前构建的节点所属的level
        while (i < s.length && s[i] == '-') { // 数数有几个连字符
            curLevel++;     // 统计它的level
            i++;            // 扫描的指针+1
        }
        let start = i;    // 记录下节点值字符串的开始位置
        while (i < s.length && s[i] != '-') { // 扫描节点值字符串
            i++;            // 扫描的指针+1
        }
        const val = s.substring(start, i); // 截取出节点值
        const curNode = new TreeNode(val); // 创建节点
        if (stack.length == 0) { // 此时栈为空，curNode为根节点
            stack.push(curNode);   // 入栈，成为栈底
            continue;              // 它没有父亲，不用找父亲，continue
        }
        while (stack.length > curLevel) {// 只要栈高>当前节点的level，就栈顶出栈
            stack.pop();
        }
        if (stack[stack.length - 1].left) { // 栈顶是父亲了，但左儿子已经存在
            stack[stack.length - 1].right = curNode; // curNode成为右儿子
        } else {
            stack[stack.length - 1].left = curNode; // 否则，成为左儿子
        }
        stack.push(curNode); // curNode自己也是父亲，入栈，等儿子
    }

    return stack[0]; // 栈底节点肯定是根节点
};