iT邦幫忙

2026 iThome 鐵人賽

DAY 13
1
Software Development

快樂演算法系列 第 13

preprocessing v5 & 297 v3

  • 分享至 

  • xImage
  •  

Because preorder traversal follows a fixed root-left-right order, and null markers preserve missing children. Using the same order during deserialization allows us to reconstruct the exact original tree unambiguously.

    1
   / \
  2   3

I visit 1 first, then 2.
Node 2 has no left or right child, so I write two null markers.
Then recursion returns to node 1 and visits node 3.
Node 3 also has two null children.

Time is O(n), because every node is processed once.
Space is O(n) for the serialized output. The recursion stack is O(h), where h is the tree height, and in the worst case h can be n.

I read characters until the delimiter. If I see a minus sign first, I store the sign separately, parse the digits into an integer, then apply the sign.


上一篇
stage update &297 v2
系列文
快樂演算法13
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

0
AndyAWD
iT邦新手 1 級 ‧ 2026-09-01 23:17:54

全英文真是快樂

我要留言

立即登入留言