Leetcode94 detailed explanation of middle order traversal of binary tree

   Previous blogs ：

Leetcode1- Detailed explanation of the sum of two numbers

Leetcode2- Detailed explanation of the code for adding two numbers

Leetcode20- Valid parentheses explain

Leetcode21- Merge two ordered linked lists

Leetcode22- Generation of valid parentheses

Leetcode24- Exchange the nodes in the linked list in pairs

Leetcode27- Remove element details

Leetcode46- Full arrangement and detailed explanation

Leetcode49- Detailed explanation of heterotopic grouping of letters

Leetcode53- Maximum subarray and explanation

Leetcode56- Detailed explanation of merging interval

LeetCode57- Insert interval explanation

Leetcode77- Detailed explanation of combination

Leetcode78- Subset explanation

Leetcode90- A subset of II Detailed explanation

---

Catalog

subject

Example

analysis

Recursive method

  Iterative method

Code

Recursive method

Iterative method

---

subject

Given the root node of a binary tree  root , return   its   Middle preface   Traverse  .

Topic analysis

It is known that ： The root node of a binary tree

Purpose ： In the sequence traversal

---

Example

Example 1

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

  Example 2

 Input ：root = []
 Output ：[]

Example 3

 Input ：root = [1]
 Output ：[1]

---

analysis

Recursive method

Traversal in middle order is to press the left subtree —> The root node —> The order of the right subtree traverses the binary tree , The left and right subtrees are traversed in the same way , Until you walk through the whole tree .

For the binary tree as shown in the figure

  The root node 1 There are left and right subtrees , The root node 2 and 3 There are also left subtrees and right subtrees

  So the traversal process is ：4—>2—>5—>1—>6—>3—>7

For recursion , That is to find the leftmost child node of the whole binary tree first , This leftmost child node is the node that no longer has left children , For the following figure, there are nodes 4, The green arrow indicates recursion , node 4 There are no left and right child nodes , At this point, we need to recurse to 2 Location of nodes , Traverse 2 The right child of the node is 5 node ,5 The node recurses to 2 node , because 2 Node left and right children to traverse all , So recurse to 1 node , At this time, the left subtree of the entire binary tree is traversed .

Empathy , Traverse the entire right subtree of a binary tree

  Iterative method

Iterative method is to use the idea of stack first out to traverse binary tree , First, traverse all left children of the left subtree , And add the left child to the stack , Until the last left child no longer has left and right nodes , At this point, take the node from the stack and put it into the result set .

The details are shown in the figure , The left child traversing the left subtree , And add it to the stack , To 4 There are no more left and right nodes , At this point 4 and 2 Add result set , To 2 There are right children when nodes , Put the right child 5 Nodes are added to the stack ,5 Nodes no longer have left and right children , take 5 Take it out of the stack and add it to the result set , The final will be 1 Take out and add to the result set , here , The left subtree is traversed completely .

  Empathy , Traversal right subtree

---

Code

Recursive method

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        self.helper(root, result)
        return result
    
    def helper(self, node, result):
        if node is None:
            return

        self.helper(node.left, result)
        result.append(node.val)
        self.helper(node.right, result)

Iterative method

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        stack = []
        cur = root

        while cur or stack:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                result.append(cur.val)
                cur = cur.right
        return result