ARTS #129

Algorithm

本周选择的算法题是：Recover a Tree From Preorder Traversal。

规则

We run a preorder depth-first search (DFS) on the root of a binary tree.

At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node. If the depth of a node is D, the depth of its immediate child is D + 1. The depth of the root node is 0.

If a node has only one child, that child is guaranteed to be the left child.

Given the output traversal of this traversal, recover the tree and return its root.

Example 1:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

Example 2:

Input: traversal = "1-2--3---4-5--6---7"
Output: [1,2,5,3,null,6,null,4,null,7]

Example 3:

Input: traversal = "1-401--349---90--88"
Output: [1,401,null,349,88,90]

Constraints:

The number of nodes in the original tree is in the range [1, 1000].
1 <= Node.val <= 109

Solution

# 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) -> Optional[TreeNode]:
        stack, i = [], 0
        while i < len(traversal):
            level, value = 0, ""
            while i < len(traversal) and traversal[i] == '-':
                level += 1
                i += 1
            while i < len(traversal) and traversal[i] != '-':
                value += traversal[i]
                i += 1
            while level < len(stack):
                stack.pop()
            
            node = TreeNode(value)
            if stack and stack[-1].left is None:
                stack[-1].left = node
            elif stack:
                stack[-1].right = node
            stack.append(node)
        return stack[0]

Review

macOS Performance Comparison: Flutter Desktop vs. Electron

Electron 是著名的跨平台解决方案，其广泛应用于各类场景中，如 VSCode、Figma、Slack 等，而 Flutter Desktop 还很新，并没有已知的大型商业应用采用它。

作者在自己的机器上对两者做了性能比较，结论如下：

Flutter 启动更快
Flutter 包体积更小，在例子中只有 Electron 的 20%
Flutter 内存/CPU/GPU/耗电量等资源占用更少
两者的 fps 差不多，都是 60fps，Flutter 略好于 Electron
…

就看未来的实际表现了。

Tip

了解一下 kitty。

借着这周的 Review，我也想从我的角度分享下对 Electron 和 Flutter 看法~

Electron：

Electron 包体积大，哪怕只是一个简单的 Hello World 应用，体积也很夸张，而且随着业务代码的不断生长，它的启动性能（启动时长、首屏渲染时间）会劣化的很厉害。不过这也不是不能避免的，就像 VSCode 做的那样，只是这个工作一定不简单
Electron 已经证明了自身的价值，只要你能写出又快又好的 Web 应用，那么 Electron 应用自然不在话下
除了包体积无法避免，资源占用量大也很难避免
Wasm 可以极大的改善特定场景下的性能表现

Flutter：

Flutter Desktop 还在 Beta 阶段，虽然性能表现好，但未经验证
Flutter 资源占用的更少，包体积也更小，并且 Dart 还在不断优化中
从开发人员规模上看，只需要 Dart 开发者就能覆盖移动端、桌面端应用了，研发成本更低
能以 FFI 执行性能敏感的任务
和 Electron 一样，对 Wasm 支持得很好

期待出现大型 Flutter 桌面级应用 :)

Algorithm

规则

Solution

Review

Tip

Share