題目連結: https://leetcode.com/problems/symmetric-tree/

Recursive version:

法ㄧ: (遞迴比較左右子樹的節點)

func isSymmetric(_ root: TreeNode?) -> Bool {
    return root == nil || helper(root?.left, root?.right)
}

func helper(_ left: TreeNode?, _ right: TreeNode?) -> Bool {
    if left == nil && right == nil {
        return true
    } else if left?.val != right?.val {
        return false
    } else {
        return helper(left?.left, right?.right) && helper(left?.right, right?.left)
    }
}

法二: (Traverse左右子樹，並把每個node的值存在array中，最後比較兩個array的值是否相同。Note: Null node仍需存0到array中，否則無法處理這個case: [1,2,2,null,3,null,3] )

// Test cases:
// nil
// [1, 2, 2]
// [1, 2, 2, 3, 4, 4, 3]
func isSymmetric(_ root: TreeNode?) -> Bool {
    guard let root = root else { return true }
    var arrLeft = [Int]()
    var arrRight = [Int]()
    traverseLeftTree(root.left, &arrLeft)
    traverseRightTree(root.right, &arrRight)
    return arrLeft == arrRight
}


func traverseLeftTree(_ root: TreeNode?, _ arr: inout [Int]) {
    guard let root = root else {
        arr.append(0)
        return
    }
    arr.append(root.val)
    traverseLeftTree(root.left, &arr)
    traverseLeftTree(root.right, &arr)
}

func traverseRightTree(_ root: TreeNode?, _ arr: inout [Int]) {
    guard let root = root else {
        arr.append(0)
        return
    }
    arr.append(root.val)
    traverseRightTree(root.right, &arr)
    traverseRightTree(root.left, &arr)
}

Iterative version

    func isSymmetric(_ root: TreeNode?) -> Bool {
        guard let root = root else { return true }
        var stackLeft: [TreeNode?] = [root.left]
        var stackRight: [TreeNode?] = [root.right]
        while !stackLeft.isEmpty && !stackRight.isEmpty {
            let left = stackLeft.removeLast()
            let right = stackRight.removeLast()
            if left == nil && right == nil {
                // do nothing
            } else if left?.val != right?.val {
                return false
            } else {
                stackLeft.append(left?.left)
                stackLeft.append(left?.right)

                stackRight.append(right?.right)
                stackRight.append(right?.left)
            }
        }
        return stackLeft.isEmpty && stackRight.isEmpty
    }