Topic:
Given a binary tree, return its prior traversal.
Example:
Input: [1, null, 2, 3]
1
\
2
/
3
Output: [1, 2, 3]
Copy the codeThe topic
Ideas:
Depth-first traversal (DFS)
- Recursively traverses the binary tree
- Push the result array in the order: root -> left -> right
/ * *
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
*}
* /
/ * *
* @param {TreeNode} root
* @return {number[]}
* /
var preorderTraversal = function(root) {
let _result = []
function dfs(node) {
if (node === null) return
_result.push(node.val)
if (node.left) dfs(node.left)
if (node.right) dfs(node.right)
}
dfs(root)
return _result
}
Copy the codeBreadth First Search (BFS)
- Starting at the root node, they are stored in an array
- Take a node and place the value of the node in the result array and push it in turn into the array (because only the left subtree is processed for its right subtree)
- If the removed node contains a left subtree, the left subtree is processed first
- If the left subtree is finished then the right subtree on all nodes is processed
var preorderTraversal = function(root) {
if (root === null) return []
let queue = [root],
_result = [],
node = queue.pop()
while(queue.length || node ! = =null) {
while(node ! =null) {
_result.push(node.val)
queue.push(node)
// Process the left subtree
node = node.left
}
node = queue.pop()
// Process the right subtree
node = node.right
}
return _result
}
Copy the codeBlog: Front end little bookboy
Every day a daily problem, write the solution of the problem will be updated to the public account one day a big Lee column welcome to pay attention to the message
Public number: front end little bookboy