Contents

[Golang][Leetcode][BinaryTree]刷題系列-94-Inorder Traversal


94. Binary Tree Inorder Traversal


Level : Easy

原題連結 : Click

題目 :

Given the root of a binary tree, return the inorder traversal of its nodes' values.


Example :

Note

Example 1:

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

Example 2:

Input: root = [] Output: []

Example 3:

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

Example 4:

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

Example 5:

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


解題思路 :

  • 這題需要我們做inorder traversal 作法與preorder類似,可以參考 leetcode144題解

  • inorder visit順序 : left -> root -> right

  • 所以不管在哪個子樹,一開始都要直接走到最左邊

  • 做binary tree traversal可以用recursive or Iterative(Stack)


Recursive解法

  • time complexity: O(n) , space complexity: O(n)

Runtime: 0 ms, faster than 100.00% of Go online submissions for Binary Tree Inorder Traversal.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func inorderTraversal(root *TreeNode) []int {
    
    var res []int
    
    var inorder func(node *TreeNode)
    
    inorder = func(node *TreeNode) {
        
        if node == nil {
            return
        }
        
        inorder(node.Left)
        res = append(res, node.Val)
        inorder(node.Right)
    }
    
    inorder(root)
    
    return res
    
}

Iterative(Stack)解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
func inorderTraversal(root *TreeNode) []int {
    
    var res []int
    
    var stack []*TreeNode
   
    if root == nil {
        return res
    }
    
    visited := root
    
    stack = append(stack, visited)
    for visited.Left != nil {
        stack = append(stack, visited.Left)
        visited = visited.Left
    
    }
    
    for len(stack) != 0 {
        
        visited = stack[len(stack)-1]

        stack = stack[:len(stack)-1]

        res = append(res, visited.Val)
        
        if visited.Right != nil {
            stack = append(stack, visited.Right)
            visited = visited.Right
            
            for visited.Left != nil {
                stack = append(stack, visited.Left)
                visited = visited.Left
            }
        }
    }
    
    return res
    
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!