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]
Explanation:
Example 2:
Input:root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output:[1,2,4,5,6,7,3,8,9]
Explanation:
Example 3:
Input:root = []
Output:[]
Example 4:
Input:root = [1]
Output:[1]
Constraints:
The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
Solutions
Solution 1: Recursive Traversal
We first visit the root node, then recursively traverse the left and right subtrees.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree. The space complexity mainly depends on the stack space used for recursive calls.
1 2 3 4 5 6 7 8 9101112131415161718
# 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 = rightclassSolution:defpreorderTraversal(self,root:Optional[TreeNode])->List[int]:defdfs(root):ifrootisNone:returnans.append(root.val)dfs(root.left)dfs(root.right)ans=[]dfs(root)returnans
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcpreorderTraversal(root*TreeNode)(ans[]int){vardfsfunc(*TreeNode)dfs=func(root*TreeNode){ifroot==nil{return}ans=append(ans,root.Val)dfs(root.Left)dfs(root.Right)}dfs(root)return}
Solution 2: Stack Implementation for Non-Recursive Traversal
The idea of using a stack to implement non-recursive traversal is as follows:
Define a stack $stk$, and first push the root node into the stack.
If the stack is not empty, pop a node from the stack each time.
Process the node.
First push the right child of the node into the stack, then push the left child of the node into the stack (if there are child nodes).
Repeat steps 2-4.
Return the result.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree. The space complexity mainly depends on the stack space.
1 2 3 4 5 6 7 8 91011121314151617181920
# 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 = rightclassSolution:defpreorderTraversal(self,root:Optional[TreeNode])->List[int]:ans=[]ifrootisNone:returnansstk=[root]whilestk:node=stk.pop()ans.append(node.val)ifnode.right:stk.append(node.right)ifnode.left:stk.append(node.left)returnans
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcpreorderTraversal(root*TreeNode)(ans[]int){ifroot==nil{return}stk:=[]*TreeNode{root}forlen(stk)>0{node:=stk[len(stk)-1]stk=stk[:len(stk)-1]ans=append(ans,node.Val)ifnode.Right!=nil{stk=append(stk,node.Right)}ifnode.Left!=nil{stk=append(stk,node.Left)}}return}
Morris traversal does not require a stack, and its space complexity is $O(1)$. The core idea is:
Traverse the binary tree nodes,
If the left subtree of the current node root is empty, add the current node value to the result list $ans$, and update the current node to root.right.
If the left subtree of the current node root is not empty, find the rightmost node pre of the left subtree (which is the predecessor of the root node in inorder traversal):
If the right subtree of the predecessor node pre is empty, add the current node value to the result list $ans$, then point the right subtree of the predecessor node to the current node root, and update the current node to root.left.
If the right subtree of the predecessor node pre is not empty, point the right subtree of the predecessor node to null (i.e., disconnect pre and root), and update the current node to root.right.
Repeat the above steps until the binary tree node is null, and the traversal ends.
The time complexity is $O(n)$, where $n$ is the number of nodes in the binary tree. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 910111213141516171819202122232425
# 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 = rightclassSolution:defpreorderTraversal(self,root:Optional[TreeNode])->List[int]:ans=[]whileroot:ifroot.leftisNone:ans.append(root.val)root=root.rightelse:prev=root.leftwhileprev.rightandprev.right!=root:prev=prev.rightifprev.rightisNone:ans.append(root.val)prev.right=rootroot=root.leftelse:prev.right=Noneroot=root.rightreturnans
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcpreorderTraversal(root*TreeNode)(ans[]int){forroot!=nil{ifroot.Left==nil{ans=append(ans,root.Val)root=root.Right}else{prev:=root.Leftforprev.Right!=nil&&prev.Right!=root{prev=prev.Right}ifprev.Right==nil{ans=append(ans,root.Val)prev.Right=rootroot=root.Left}else{prev.Right=nilroot=root.Right}}}return}