LeetCode 双刀流：144. Binary Tree Preorder Traversal

144. Binary Tree Preorder Traversal

今天挑选的是一题「二元树（Binary Tree）」，二元树相对於二元搜寻树来说条件相对没有那麽严谨。这题想考的是「前序遍历（Preorder Traversal）」，遍历是指要走过树中每一点的方式，但是因为树中每一个节点可能会有左/右分支，因此会有「要先找左边还是右边」、「要找到最底还是先把周围的找完」等等的衍生议题。常见的遍历方法可以分为「前序」、「中序」跟「後序」，依据 Root 被找到的先後做排序。

先看一下题目描述

Given the root of a binary tree, return the preorder traversal of its nodes' values.

再搭配范例理解题目

• Example 1:

Input: root = [1,null,2,3]
Output: [1,2,3]

这个题目单纯就是实作「前序遍历（Preorder Traversal）」，算是对於二元树的基本操作。所谓的前序遍历就是先找出「中间节点」、再找「左边节点」、最後才找「右边节点」以此类推。

开始实作

方法 ①：Brute force

第一个方法可以用两个回圈硬干，用两层回圈探访全部的节点。里面的回圈去找每一个点当中的「中间节点」和「左边节点」，接着再从外层的回圈去找到「右边节点」。

用 Python 实作一次

class Solution:
    def preorderTraversalRecursive(self, root: TreeNode) -> List[int]:
        stack, result = [], []
        
        while stack or root:
            while root:
                result.append(root.val)
                stack.append(root)
                root = root.left
            root = stack.pop()
            root = root.right
        
        return result

也可以用 JavaScript 复刻一次

var preorderTraversal = function(root) {
    if(!root) return []; 
    let res = [], stack = [];
    let cur = root;
    while(cur || stack.length) {
        while(cur) {
            res.push(cur.val);
            stack.push(cur.right);
            cur = cur.left;
        }
        cur = stack.pop();
    }
    return res;
};

方法 ②：递回（recursion）

第二种方法搭配 Recursive 的概念，取得「中间节点」之後，再往下的「左边节点」找、找完再找「右边节点」，利用递回对每一个点都做一样的规则。

用 Python 实作一次

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        res = [root.val]
        res.extend(self.preorderTraversal(root.left));
        res.extend(self.preorderTraversal(root.right));
        return res

也可以用 JavaScript 复刻一次

const preorderTraversal = (root) => {
    if (!root) return [];
    let res = [root.val];
    res.push(...preorderTraversal(root.left));
    res.push(...preorderTraversal(root.right));
    return res
};

反思沉淀

遍历是树（Tree）特性的一种延伸操作，不同於线性的搜寻，因为每一个节点可能会有左/右分支，因此有不同的先後顺序找法。而不同的找法有时候可以搭配资料结构的特性来使用，以本题来说，我们可以转换成对每一个点都做一样的操作，就可以利用递回的方式实现。

举一反三看看相似题

最後可以从题目提供的相似题看一下有哪些类似的题目，适合作为你下一个尝试的练习：

• 94. Binary Tree Inorder Traversal
• 589. N-ary Tree Preorder Traversal

嗨，大家好！我是维元，一名擅长网站开发与资料科学的双栖工程师，斜杠於程序社群【JSDC】核心成员及【资料科学家的工作日常】粉专经营。目前在 ALPHACamp 担任资料工程师，同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验，持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享，邀请你加入 订阅 接收最新资讯。