[LeetCode] 94. Binary Tree Inorder Traversal / Swift

[문제 보기]

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]

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]

 

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?

 

https://leetcode.com/problems/binary-tree-inorder-traversal/

Binary Tree Inorder Traversal - LeetCode

 

---

1. 재귀로 트리 순회

2. 반복문으로 트리 순회

 

// 1. 재귀버전

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    var ans = [Int]()
    
    func travel(_ node: TreeNode?) {
        if node == nil {
            return
        }
        
        travel(node!.left)
        ans.append(node!.val) // 중위순회
        travel(node!.right)
    }
    
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        travel(root)
        return ans
    }
}

 

 

// 2. 반복문으로 이진트리 순회(중위순회)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        var ans = [Int]()
        var stack = [TreeNode]()
        var current = root
        while !stack.isEmpty ||  current != nil {
            while current != nil {
                stack.append(current!)
                current = current!.left
            }
            
            let top = stack.removeLast()
            ans.append(top.val)
            current = top.right
        }
        
        return ans
    }
}