leetcode-Easy-29-Tree-Same tree

1427 단어

제목은 두 갈래 나무가 똑같은지 아닌지를 판단한다


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
    
    
  • 해법
  • var isSameTree = function(p, q) {
      //BFS
      function getBfsPath(root){
        let path = []
        let nodes = []
        nodes.push(root)
        while(nodes.length > 0){
          let node = nodes.shift()
          if(!node){
            path.push(null)
          }else{
            path.push(node.val)
            nodes.push(node.left)
            nodes.push(node.right)
          }
          
      }
        return path
      }
      //  
      function arrayEqual(arr1,arr2){
        const flag =  arr1.length === arr2.length && arr1.every((val,idx) => val === arr2[idx])
        return flag
      }
      return arrayEqual(getBfsPath(p),getBfsPath(q))
    };
    
  • 제목 사고방식은 광범위한 우선 검색(BFS)을 이용하여 두 노드의 수조 경로를 얻어낸 다음에 일일이 비교한다
  • 좋은 웹페이지 즐겨찾기