Swift solution - DFS, BFS


  • 0
    class Solution {
        func isSymmetric_BFS(_ root: TreeNode?) -> Bool {
            guard let root = root else {
                return true
            }
            
            let nilNode = TreeNode(-1)
            var queue1 = [TreeNode]()
            var queue2 = [TreeNode]()
            
            if let leftNode = root.left {
                queue1.append(leftNode)
            } else {
                queue1.append(nilNode)
            }
            if let rightNode = root.right {
                queue2.append(rightNode)
            } else {
                queue2.append(nilNode)
            }
            while !queue1.isEmpty && !queue2.isEmpty {
                let left = queue1.removeFirst()
                let right = queue2.removeFirst()
                if left === nilNode && right === nilNode {
                    continue
                }
                if left === nilNode || right === nilNode {
                    return false
                }
                if left.val != right.val {
                    return false
                }
                if let leftLeftNode = left.left {
                    queue1.append(leftLeftNode)
                } else {
                    queue1.append(nilNode)
                }
                if let leftRightNode = left.right {
                    queue1.append(leftRightNode)
                } else {
                    queue1.append(nilNode)
                }
                if let rightRightNode = right.right {
                    queue2.append(rightRightNode)
                } else {
                    queue2.append(nilNode)
                }
                if let rightLeftNode = right.left {
                    queue2.append(rightLeftNode)
                } else {
                    queue2.append(nilNode)
                }
            }
            
            return true
        }
        
        func isSymmetric_DFS(_ root: TreeNode?) -> Bool {
            guard let root = root else {
                return true
            }
            
            return helper(root.left, root.right)
        }
        
        func helper(_ left: TreeNode?, _ right: TreeNode?) -> Bool {
            guard let leftNode = left, let rightNode = right else {
                return left === right
            }
            
            if leftNode.val != rightNode.val {
                return false
            }
            
            return helper(leftNode.left, rightNode.right) && helper(leftNode.right, rightNode.left)
        }
    }
    

Log in to reply
 

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