Swift 3 iterative and recursive methods


  • 0
    Y
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     public var val: Int
     *     public var left: TreeNode?
     *     public var right: TreeNode?
     *     public init(_ val: Int) {
     *         self.val = val
     *         self.left = nil
     *         self.right = nil
     *     }
     * }
     */
    class Solution {
        // iterative method using stack
        func inorderTraversal(_ root: TreeNode?) -> [Int] {
            // use a stack
            var stack = [TreeNode]()
            var ans = [Int]()
            var node = root
            while node != nil || !stack.isEmpty {
                // go to left 
                while node != nil {
                    stack.append(node!)
                    node = node!.left
                }
                // now node == nil, pop from stack, get the inorder 
                node = stack.removeLast()
                ans.append(node!.val)
                node = node!.right
            }
            return ans
        }
        
        
        // DFS
        func inorderTraversalDFS(_ root: TreeNode?) -> [Int] {
            var ans = [Int]()
            inorder(root, &ans)
            return ans
        }
        
        func inorder(_ root: TreeNode?, _ ans: inout [Int]) {
            guard let root = root else { return } // root == nil
            inorder(root.left, &ans)
            ans.append(root.val)
            inorder(root.right, &ans)
        }
        
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.