Given the root of a binary tree, return the inorder traversal of its nodes' values.
Example 1:
Input:root = [1,null,2,3]
Output:[1,3,2]
Explanation:
Example 2:
Input:root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output:[4,2,6,5,7,1,3,9,8]
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 recursively traverse the left subtree, then visit the root node, and finally recursively traverse the right subtree.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree, and the space complexity mainly depends on the stack space of the recursive call.
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:definorderTraversal(self,root:Optional[TreeNode])->List[int]:defdfs(root):ifrootisNone:returndfs(root.left)ans.append(root.val)dfs(root.right)ans=[]dfs(root)returnans
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcinorderTraversal(root*TreeNode)(ans[]int){vardfsfunc(*TreeNode)dfs=func(root*TreeNode){ifroot==nil{return}dfs(root.Left)ans=append(ans,root.Val)dfs(root.Right)}dfs(root)return}
Solution 2: Stack Implementation for Non-recursive Traversal
The non-recursive approach is as follows:
Define a stack stk.
Push the left nodes of the tree into the stack in sequence.
When the left node is null, pop and process the top element of the stack.
Repeat steps 2-3.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree, and the space complexity mainly depends on the stack space.
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:definorderTraversal(self,root:Optional[TreeNode])->List[int]:ans,stk=[],[]whilerootorstk:ifroot:stk.append(root)root=root.leftelse:root=stk.pop()ans.append(root.val)root=root.rightreturnans
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcinorderTraversal(root*TreeNode)(ans[]int){stk:=[]*TreeNode{}forroot!=nil||len(stk)>0{ifroot!=nil{stk=append(stk,root)root=root.Left}else{root=stk[len(stk)-1]stk=stk[:len(stk)-1]ans=append(ans,root.Val)root=root.Right}}return}
Solution 3: Morris Implementation for In-order Traversal
Morris traversal does not require a stack, so the space complexity is $O(1)$. The core idea is:
Traverse the binary tree nodes,
If the left subtree of the current node root is null, 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 null, find the rightmost node prev of the left subtree (which is the predecessor node of the root node in in-order traversal):
If the right subtree of the predecessor node prev is null, 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 prev is not null, add the current node value to the result list ans, then point the right subtree of the predecessor node to null (i.e., disconnect prev 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)$, and the space complexity is $O(1)$. Here, $n$ is the number of nodes in the binary tree.
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:definorderTraversal(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:prev.right=rootroot=root.leftelse:ans.append(root.val)prev.right=Noneroot=root.rightreturnans
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcinorderTraversal(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{prev.Right=rootroot=root.Left}else{ans=append(ans,root.Val)prev.Right=nilroot=root.Right}}}return}