Given a root node root of a binary tree, return its inorder traversal .
Input: root = [1,null,2,3]
The number of nodes in the tree is in the range [0, 100]
-100 <= Node.val <= 100
Advanced: The recursive algorithm is simple, can you do it with an iterative algorithm?
Knowledge point review:
Pre/preorder traversal: root left right
Inorder traversal: left root right
Postorder Traversal: Left Right Root
Method 1: recursive implementation
Recursive implementation is too simple
- Preorder traversal: print - left - right
- Inorder traversal: left - print - right
- Post-order traversal: left-right-print
The title requires in-order traversal, then the tree can be traversed in the order of left-print-right. The recursive function is implemented
- Termination condition: when the current node is empty
- Inside the function: recursively call the left node, print the current node, and then recursively call the right node
Time complexity: O(n)
Space complexity: O(h), h refers to the height of the tree
# 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 = right class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: res =  def dfs(root): if not root: return # follow left-Print-right way traversal dfs(root.left) res.append(root.val) # Pay attention to the value writing " root.val" dfs(root.right) dfs(root) return res
Method 2: Iterative Implementation
The real difficulty of this problem is how to do it in a non-recursive way.
The recursive implementation is that the function calls itself, and the calls are nested layer by layer. The operating system automatically helps us to use the stack to save each called function. Now we need to simulate such a calling process by ourselves.
The recursive calling process is as follows:
dfs(root.left) dfs(root.left) dfs(root.left) for null return # print node dfs(root.right) dfs(root.right) dfs(root.right) ......
The recursive calling process is to keep walking to the left. When the left side can't go any further, it prints the node, turns to the right, and then continues the process on the right.
When we implement iteratively, we can use the stack to simulate the above calling process.
Time complexity: O(n),
Space complexity: O(h), where h is the height of the tree.
# 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 = right class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: res =  stack =  while stack or root: # Keep walking in the direction of the left subtree, and save the current node to the stack every time you walk # This is the call to simulate recursion if root: stack.append(root) root = root.left # The current node is empty, indicating that the left side has come to the end, pop the node from the stack and save it # Then turn to the right node and continue the whole process above else: tmp = stack.pop() res.append(tmp.val) # Pay attention to the writing of the value root = tmp.right return res
Method 3: Morris Traversal
Auxiliary space is used both recursively and iteratively, and Morris traversal has the advantage that no auxiliary space is used. The disadvantage is that the structure of the entire tree is changed, and a binary tree is forcibly changed into a linked list structure.
We attach the yellow area to the right subtree of node 5 (orange arrow), and then attach the two nodes 2 and 5 to the right of node 4. In this way, the entire tree basically becomes a linked list, and then it continues to traverse to the right.
Time complexity: O(n), the complexity of finding each predecessor node is O(n), because the binary tree of n nodes has n-1 edges, and each edge can only be used twice (once to locate the node, Find the predecessor node at a time), so the time complexity is O(n).
Space complexity: O(1), no additional auxiliary space is used.
# 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 = right class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: res =  pre = None while root: # If the left node is not empty, hang the current node and the right subtree below the rightmost subtree of the left node if root.left: pre = root.left while pre.right: pre = pre.right pre.right = root # Will root direction root of left tmp = root root = root.left tmp.left = None # If the left subtree is empty, print this node and traverse to the right else: res.append(root.val) root = root.right return res # author: wang_ni_ma # Link: https://leetcode.cn/problems/binary-tree-inorder-traversal/solution/dong-hua-yan-shi-94-er-cha-shu-de-zhong-xu-bian-li/ # Source: Likou ( LeetCode) # Copyright belongs to the author. For commercial reprints, please contact the author for authorization, and for non-commercial reprints, please indicate the source.