Swift) LeetCode(Easy) - Symmetric Tree (BFS&Recursive)

leetcode.com/problems/symmetric-tree/

Symmetric Tree - LeetCode

개인적으로 쫌 어려웠습니다 ㅎㅎㅎㅎ

Easy 문제인데,,, 처음으로 배열형 트리가 아닌 리스트로 된 트리 문제를 푸는 것이고

대칭인지 아닌지 비교하는 것은 처음이여서,,,

** 문제 **

문제는 간단합니다. 루트 노드를 기준으로 반으로 접었을 때, 대칭이 되면 됩니다.

 

** 해결 방법 ** 

일단 ,,, 이 코드가 잘 돌아가는지,, 아닌지 구분을 하기 위해서는

트리를 만들 필요가 있었는데,,, 어떻게 트리를 만들지??? 고민하다가 

    func makeTree(_ array : [Int?]) -> TreeNode?{
        
        if array.isEmpty {return nil}
        
        var sequence : [TreeNode?] = []
        
        let startNode = TreeNode(array[0])
            
        var flag = "left"
        
        for element in array{
            
            if sequence.isEmpty {
                sequence.append(startNode)
                sequence.append(startNode)
                continue
            }
            
            
            if let node = sequence[0] {
                sequence.remove(at: 0)
                let newNode = TreeNode(element)
                if flag == "left"{
                           
                    node.left = newNode
                    sequence.append(node.left)
                    sequence.append(node.left)
                    flag = "right"
                }
                else {
                    
                    node.right = newNode
                    sequence.append(node.right)
                    sequence.append(node.right)
                    flag = "left"
                }
                
            }
            
        }
             
        return startNode
    }
    
    

이렇게 풀었습니다,,,,, 배열을 담아 하나식 연결 해주는 방식 입니다.

이때 같은 주소를 두번 씩 넣어주는 이유는, 이진 트리 이기 때문에, 자식도 두번이라서

노드의 왼쪽, 노드의 오른쪽 이렇게 두번 들어가야하기 때문입니다. 

 

그래서 이렇게 트리를 만들고,,,,, 어찌저찌 

    func isSymmetric2(_ root: TreeNode?) -> Bool {
        
        guard let root = root else {return true}
        
        if root.left == nil && root.right == nil {return true}
        
        var sequence : [TreeNode?] = [root]
        
        while !sequence.isEmpty{
            
            var nodesValue : [TreeNode?] = []
            var flag = false
            
            for element in sequence {
                
                let leftNode = element?.left
                let rightNode = element?.right
                nodesValue.append(leftNode)
                nodesValue.append(rightNode)
                
                if leftNode != nil || rightNode != nil {
                    flag = true
                }
                
            }
            
            if flag == false {
                break
            }
            
            sequence.removeAll()
            
            for element in 0...(nodesValue.count - 1)/2 {
                
                if let startnode = nodesValue[element] , let lastNode = nodesValue[nodesValue.count - 1 - element] {
                    
                    if startnode.val != lastNode.val {
                        return false
                    }
                    
                }
                else if nodesValue[element] != nil && nodesValue[nodesValue.count - element - 1] == nil{
                    return false
                }
                else if nodesValue[element] == nil && nodesValue[nodesValue.count - element - 1] != nil{
                    return false
                }
            }
            
            sequence = nodesValue
            
        }
       
        
        return true
    }

지저분하지만,,, BFS랑 비슷하게 풀었습니다 ㅎㅎㅎㅎ 

아마 저만 알아 볼 수 있을 것 입니다 ㅎㅎㅎ

 

결국 다른 사람의 코드를 보고  좋은 해결 법임을 느끼고 

비슷하게 다시 만들어서 풀었습니다.

    func isSymmetric(_ root: TreeNode?) -> Bool {
     
        return isMirrored(root, root, true)
        
    }
    
    func isMirrored(_ leftNode : TreeNode? , _ rightNode : TreeNode?, _ isStart : Bool) -> Bool {
        
        guard let left = leftNode , let rigth = rightNode else {
            return leftNode == nil && rightNode == nil
        }
        
        if isStart == true {
        
            return left.val == rigth.val && isMirrored(left.left, rigth.right, false)
        }
        
        return left.val == rigth.val && isMirrored(left.right, rigth.left, false) && isMirrored(left.left, rigth.right, false)
    }

 

** 다른 사람의 코드 ** 

prashant1207-

class Solution {
    func isSymmetric(_ root: TreeNode?) -> Bool {
        guard let root = root else {
            return true
        }
        
        return isMirror(root, root)
    }
    
    func isMirror(_ first: TreeNode?, _ second: TreeNode?) -> Bool {
         guard let firstVal = first?.val, let secondVal = second?.val else {
            return first == nil && second == nil
        }
        
        return (firstVal == secondVal) && isMirror(first?.right, second?.left) && isMirror(first?.left, second?.right)
    }
}