두 갈래 나무의 귀속과 교체

알고리즘을 처리할 때, 통상적으로 귀속 방법이나 교체 방법 사이에서 선택해야 한다.비록 일부 문제나 언어는 자연히 다른 방법이 아니라 한 방법에 경향이 있지만, 실제로는 서로 바꾸어 사용할 수 있다.이것은 모두 어떻게 문제를 구축하는지 이해하는 문제다.
반복과 교체는 정지 조건에 도달할 때까지 코드를 실행합니다.귀속을 사용하면 정지 조건에 도달할 때까지 같은 함수를 반복해서 호출 창고에서 값을 되돌릴 수 있습니다.호출 창고를 구축하는 것이 아니라 교체를 사용하면 특정한 데이터 구조에 데이터를 저장할 수 있습니다. 보통 창고나 대기열입니다. 그리고 정지 조건이 충족될 때까지 순환을 실행할 수 있습니다.
이러한 생각을 더욱 구체적으로 하기 위해서, 두 갈래 나무가 대칭적인지 확인하는 두 가지 해결 방안이 있다. 하나는 귀속적인 것이고, 다른 하나는 교체된 것이다.만약 당신이 그곳에서 자신의 해결 방안을 제출하고 싶다면, 이 문제는 Leetcode!두 갈래 나무는 귀속 구해에 매우 유리하다. 왜냐하면 두 갈래 나무의 모든 부분은 단지 다른 두 갈래 나무이기 때문이다.그러나 교체 방법을 사용할 수도 있고 이런 상황에서 대열을 이용할 수도 있다.
이것은 기본적인 문제이다. 만약 두 갈래 검색 트리가 그 중심의 거울이라면, 그것은 대칭적이다.그래서 이 나무는 대칭적이다.

하지만 이 나무는

트리 클래스가 정의되었습니다. left, right 및 val 속성을 사용할 수 있습니다.

 //Definition for a binary tree node.
 function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
 }

트리의 루트 노드를 지정합니다. 문제는 이 트리가 대칭적인지 확인하는 알고리즘을 작성하는 것입니다.어떤 방법을 사용하든지 간에 해결 방안은 왼쪽 지점의 왼쪽 지점이 오른쪽 지점의 오른쪽 지점(left.left === right.right과 같은지, 왼쪽 지점의 오른쪽 지점이 오른쪽 지점의 왼쪽 지점(left.right === right.left과 같은지 확인해야 한다.이 조건이 각 하위 트리에 적용되는 경우 left 및 right 는 서로 대칭적으로 표시됩니다.
우선 귀속해를 봅시다.이 해결 방안에서 하위 함수는 left과right를 매개 변수로 하고 이 값을 비교한 다음에 이 노드의 좌우 하위 노드에서 자신을 호출한다.다음은 전체 구현입니다.

const isSymmetric = root => {
  function compare(left, right) {
    if (left === null && right === null) {
      return true
    } else if (left === null || right === null || left.val !== right.val) {
      return false
    } else {
      return compare(left.left, right.right) && compare(left.right, right.left)
    }
  }
  if (root === null) {
    return true
  }
  return compare(root.left, root.right)
};

호출 compare 전에 뿌리가 나무인지 확인합니다.만약 없다면, 할 일이 없다.그러나 가령, 우리는 root.left과root.right부터 차례로 호출되기 시작한다.우선, 우리는 left과right가 모두null인지 검사합니다. 만약 그들이 실제로 트리 노드가 아니라면, 우리는 .left또는.right을 호출할 수 없습니다!이것은 우리의 정지 조건 중 하나입니다. 좌우 위치의 일치null값이 대칭 트리의 표준을 충족시키기 때문에 true 호출 창고로 되돌아옵니다.다음 줄에서 대칭 트리 위반을 검사합니다.마찬가지로null값.left과.right를 호출할 수 없기 때문에 우선 이런 상황을 검사합니다.값이 일치하지 않으면 트리가 대칭적이지 않고 false 호출 창고로 되돌아옵니다.이것은 두 가지 정지 조건이다.마지막으로 이 두 조건이 모두 충족되지 않으면 트리의 각 지점 compare 함수를 차례로 호출합니다.&& 외부 함수를 호출하는 쌍방이 모두true로 돌아가야 true로 돌아갈 수 있도록 확보합니다. - 내부 호출이 false로 해석되면 호출 창고와 최종 반환 false 함수를 위로 전달합니다.
중요한 것은 귀속 해결 방안에서 내부 반환 값은 반드시 호출 창고에 전달되어야 한다는 것을 기억해야 한다!JavaScript에 암시적 반환이 없으므로 compare 반복 호출도 명시적으로 반환해야 합니다.return의 사용은 귀속해와 교체해 사이의 관건적인 차이 중 하나이다. 이제 교체해를 보자.

const isSymmetric = root => {
  if (root === null) {
    return true
  }
  let queue = []
  queue.push(root.left, root.right)

  while (queue.length > 0) {
    let left = queue.shift()
    let right = queue.shift()
    if (left === null && right === null) {
      continue
    } else if (left === null || right === null || left.val !== right.val) {
      return false
    } else {
      queue.push(left.left, right.right, left.right, right.left)
    }
  }
  return true
}

마찬가지로 첫 번째 단계는 우리가 트리 노드를 시작해야 한다는 것을 확인하는 것이다.만약 우리가 이렇게 한다면, 우리는 root.left 와 root.right 를 가진 대기열을 시작합니다.따라서 코드 논리는 귀속 해결 방안과 거의 같다.가장 큰 차이점은 호출 창고를 구축하는 것이 아니라 대기열에 노드를 추가하고 while 순환을 실행해서 대기열이 비어 있을 때까지 하는 것이다.또 다른 중요한 차이점은 return의 사용이다.첫 번째 조건left === null && right === null에서 우리는 순환을 멈추고 되돌아오는 것이 아니라 다른 노드를 계속 검사하기를 희망한다true.귀환true은 순환에서 벗어나 true 함수에서 귀환isSymmetric합니다. 호출 창고에 숨겨져 있지 않기 때문입니다.어디서 사용하는지 알고 return 끝나는 함수는 교체와 귀속 해결 방안을 구축하는 관건이다.다른 한편, 다음 조건에서 false 조건을 찾으면 우리는 완성합니다!우리는 확실히 while 순환을 끝내고 즉시 돌아오기를 희망한다.false 조건을 찾지 못한 경우에만 마지막 줄에 도착해서 false 로 돌아갈 수 있습니다.
나는 이것이 귀속과 교체 사이에서 이동하는 구체적인 예시를 제공하기를 바란다.나에게 있어서 이해true가 무엇을 하고 있는지, 그리고 서로 다른 정지 조건이 이 두 가지 방법 사이에서 이동하는 관건이다.
읽어주셔서 감사합니다!