[Binary tree] LeetCode 94. Inorder traversal of binary tree [simple]

Given a root node root of a binary tree, return its inorder traversal .

Example 1:

 

Input: root = [1,null,2,3]
Output: [1,3,2]


Example 2:

Input: root=[]
output: []


Example 3:

Input: root=[1]
Output: [1]
 

hint:

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?

[analyze]

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.

 

Tags: CODING

Posted by pck76 on Wed, 11 May 2022 11:33:26 +0300