💯 Daily LeetCode Challenge Day_13 - Same Tree

 

---

문제

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

---

dfs로 tree를 순회하면 순회 순서가 같아도 두가지 경우일 때 tree의 모양이 달라질 수 있다.

• 왼쪽 leaf 인지 오른쪽 leaf 인지 (example2)
• leaf 방향은 같은데 depth 가 다른지 ([10,5,15] [10,5,null,null,15])

dfs 로 traverse 하면서 leaf side 와 depth 를 저장할 수 있는 튜플을 만들어 배열에 저장했다.

마지막으로 배열을 순회하며 튜플 요소중 다른게 있으면 return false 했다.

/**
 * 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 arr1 : [(Int,Int,Int)] = []
    var arr2 : [(Int,Int,Int)] = []
    func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        if p == nil && q == nil {
            return true
        }else if p == nil && q != nil {
            return false
        }else if p != nil && q == nil {
            return false
        }
        dfs(p!,0,0,0)
        dfs(q!,0,1,0)
        for i in 0..<arr1.count{
            if (arr1[i].0 == arr2[i].0 && arr1[i].1 == arr2[i].1 && arr1[i].2 == arr2[i].2) == false {
                return false
            }
        }
        return true
    }
    func dfs(_ tree : TreeNode, _ side : Int, _ treeKind : Int, _ depth : Int){
        //p: 0 q: 1
        //center: 0, left: 1 right: 2
        if treeKind == 0 {arr1.append((tree.val,side,depth))}
        if treeKind == 1 {arr2.append((tree.val,side,depth))}
        if tree.left != nil {
            dfs(tree.left!,1,treeKind,depth+1)
        }
        if tree.right != nil {
            dfs(tree.right!,2,treeKind,depth+1)
        }
    }
}

 

좋은 해답은 아닌것 같은게 두개의 tree를 동시에 하나씩 순회하며 다른 부분이 나오는 즉시 return false 를 하면 좋을 것 같은데 내 코드는 트리의 구조가 같던 다르던 무조건 tree size *2 번을 traverse 해야 한다. (tree 자체 + 방문배열).

좀더 생각해 봐야겠다.