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]
Example 2:
Input: root = [] Output: []
Example 3:
Input: root = [1] Output: [1]
solution:
1. 首先,我們要知道 Preorder traversal(前序遍歷)所指的方向,接著:
2. 我們在 preorderTraversal(root) 的函式中接受 binary tree 的輸入,並透過 dfs 來完成前序遍歷的結果。
3. 在 dfs(node, result) 中,我們先判斷 node 是否為 null,如果是則直接返回。
4. 如果 node 不是 null,代表該節點有值,我們開始做前序遍歷:
4-1. result.push(node.val): 將當前節點的值加入到 result 陣列中。
4-2. dfs(node.left, result): 使用遞迴對左子樹進行前序遍歷,持續走到左子樹最底層。
4-3. dfs(node.right, result): 使用遞迴對右子樹進行前序遍歷。
5. 這種遍歷方式首先訪問當前節點,然後遍歷左子樹,最後遍歷右子樹。這一切都是遞迴的方式來完成。
ex. 中序遍歷步驟: 1. 訪問當前節點 2. 遍歷左子樹(直至最底層) 3. 遍歷右子樹 附上示意圖: https://ithelp.ithome.com.tw/articles/10289291
Code 1: DFS
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } } var preorderTraversal = function(root) { let result = []; dfs(root, result); return result; } function dfs(node, result) { if (!node) return; result.push(node.val); dfs(node.left, result); dfs(node.right, result); } //如自行在 replit 的 repo 上測試時,需額外進行 arrayToTreeNode 的轉換,代碼如下: function arrayToTreeNode(arr) { if (!arr.length) return null; const root = new TreeNode(arr[0]); const queue = [root]; let i = 1; while (queue.length && i < arr.length) { const current = queue.shift(); ['left', 'right'].forEach((direction) => { if (i < arr.length && arr[i] !== null) { current[direction] = new TreeNode(arr[i]); queue.push(current[direction]); } i++; }); } return root; }
FlowChart:
Example 1
const rootNode = new TreeNode( 1, null, new TreeNode( 2, new TreeNode(3), null, ) ); const rootNode = new TreeNode( 1, new TreeNode(2) new TreeNode(3) );
Example 2
const rootNode = []
Example 3
TreeNode { val: 1, left: null, right: null }
Code 2: DFS