두 갈래 나무의 세 가지 범람하는 귀속과 교체 해법

두 갈래 나무의 정의와 두 갈래 나무가 무엇인지에 대한 세 가지 역력(선순 역력, 중순 역력, 후순 역력)은 본고가 주목하는 중점이 아니므로 관련 자료를 직접 찾아보세요.본고의 중점은 어떻게 귀속과 교체로 두 갈래 나무의 세 가지 역행을 실현하는가이다.
leetcode에는 세 가지 문제가 있는데 각각 세 가지 범람 결과를 구한다. 비나리 Tree Preorder Traversal, 비나리 Tree Inorder Traversal, 비나리 Tree Postorder Traversal이다.

귀속

귀속 해법은 더 이상 말할 필요가 없고 귀속 부분의 다른 위치에서 노드value를 수조에 설치하면 된다.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
function dfs(root, ans) {
  if (!root) return;

  //  
  // ans.push(root.val);

  dfs(root.left, ans);

  //  
  // ans.push(root.val);
  dfs(root.right, ans);

  //  
  // ans.push(root.val);
}

var preorderTraversal = function(root) {
  var ans = [];
  dfs(root, ans);
  return ans;
};

번갈아

어려운 점은 교체다.
만약에 두 갈래 나무를 그림으로 간주한다면 두 갈래 나무의 범람은 사실 그림의 깊이를 우선적으로 범람하는 것이다. 그림의 깊이를 우선적으로 범람하는 것은 수동 시뮬레이션 창고로 풀 수 있다면 두 갈래 나무의 범람도 가능하다.
창고 아날로그 그림의 깊이를 우선적으로 훑어보고 아버지 노드의 아들 노드 하나를 창고에 넣고 아들 노드를 삭제합니다
아버지 노드의 모든 아들 노드가 삭제되었을 때, 아버지 노드는 창고에서 나왔다
우리는 아래의 두 갈래 나무로 예를 들자.

      1
    /  \
   2    5
  / \
 3   4

어떻게 창고로 이 두 갈래 나무를 두루 훑어보는 것을 시뮬레이션합니까?우리는 stack수 그룹 아날로그 창고를 사용한다.

루트를 창고에 넣습니다.이때stack = [1]

루트의 하위 노드를 옮겨다니며 왼쪽 하위 노드를 창고에 넣습니다.stack = [1, 2]

이때 창고 꼭대기 요소는 2로 하위 노드를 훑어보기 시작합니다.왼쪽 서브노드3로 입고됩니다.stack = [1, 2, 3]

이때 창고 꼭대기 요소는 3이고 하위 노드가 없어서 창고에서 꺼냅니다.stack = [1, 2]

이때 창고 꼭대기 요소는 2로 그의 하위 노드를 두루 돌아다닌다.왼쪽 노드가 이미 두루 다니기 때문에 오른쪽 노드는 창고에 들어간다.stack = [1, 2, 4]

이때 창고 꼭대기 요소는 4이고 3와 마찬가지로 좌우 노드가 없어서 창고에서 나온다.stack = [1, 2]

이때 창고 꼭대기 요소는 2이고 아버지 노드의 모든 아들 노드가 삭제될 때 아버지 노드가 창고에서 나가고 아버지 노드가 창고에서 나온다.stack = [1]

이때 창고 꼭대기 요소는 1이고 그의 왼쪽 노드는 이미 옮겨다니고 오른쪽 노드를 옮겨다니며 5를 창고에 넣는다.stack = [1, 5]

이때 창고 꼭대기 요소는 5이고 하위 노드가 없어서 창고에서 나온다.stack = [1]

이때 창고 꼭대기 요소는 1이고 그의 하위 노드는 모두 옮겨다니며 창고에서 나온다.stack=[]

이때 Stack 수조의 길이는 0이고 교체가 끝납니다.

선착순 반복

먼저 순서대로 반복하면 위의 절차에 따라 아날로그 창고를 모의하고, 매번 창고에 들어갈 때마다 노드의value 값을 ans 그룹에 넣으면 됩니다.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */

var preorderTraversal = function(root) {
  if (!root) return [];

  var stack = []  //  
    , ans = [];

  stack.push(root);
  ans.push(root.val);

  while (stack.length) {
    var elem = stack[stack.length - 1];
    if (elem.left) {
      ans.push(elem.left.val);
      stack.push(elem.left);
      elem.left = null;
    } else if (elem.right) {
      ans.push(elem.right.val);
      stack.push(elem.right);
      elem.right = null;
    } else
      stack.pop();
  }

  return ans;
};

두 갈래 나무의 부 노드가 가장 많으면 두 개의 자 노드가 있기 때문에 두 개의 노드를 직접 훑어보고 창고에서 부 노드를 삭제하면 된다.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */

var preorderTraversal = function(root) {
  if (!root) return [];

  var stack = []  //  
    , ans = [];

  stack.push(root);

  while (stack.length) {
    var elem = stack.pop();
    ans.push(elem.val);
    
    if (elem.right)
      stack.push(elem.right);

    if (elem.left)
      stack.push(elem.left);
  }

  return ans;
};

후순 반복

선착순 범람과 약간 다른 것은 선착순 범람은 부모 노드를 먼저 범람하기 때문에 부모 노드의value값은 창고에 들어갈 때ans수조를 넣고, 후착순 범람은 마지막에 부모 노드를 범람하기 때문에 부모 노드가 창고에서 나올 때(이때 좌우 트리가 이미 범람이 완료됨) 노드의value값을 ans수조에 넣으면 된다.

var postorderTraversal = function(root) {
  if (!root) return [];

  var stack = []  //  
    , ans = [];

  stack.push(root);

  while (stack.length) {
    var elem = stack[stack.length - 1];
    if (elem.left) {
      stack.push(elem.left);
      elem.left = null;
    } else if (elem.right) {
      stack.push(elem.right);
      elem.right = null;
    } else {
        var a = stack.pop();
        ans.push(a.val);
      }
  }
  return ans;
};

중순 스트리밍

중서 두루두루는 3대 두루 중에서 가장 복잡하다.선착순 범람은 부모 노드를 먼저 범람하기 때문에 노드가 창고에 들어갈 때value값을 저장하고, 후착순 범람은 마지막에 부모 노드를 범람하기 때문에 노드가 창고에서 나올 때value값을 저장하고, 중착순 범람은?
leetcode에서 중순으로 이 문제를 훑어보는 것은 선순과 후순보다 tag-hashtable가 하나 더 많은데 어떻게hash를 하는지도 바로 이 문제의 난점이다.중순 스트리밍은 부모 노드의 왼쪽 트리가 스트리밍된 후에 부모 노드의value 값을 ans 그룹에 저장합니다. 그러면 왼쪽 트리가 스트리밍이 끝난 것을 어떻게 판단합니까?
예를 들어 아래의 두 갈래 나무:

      1
    /  \
   2    5
  / \
 3   4

2 이 노드를 훑어보았을 때 왼쪽 노드가 있다. 선순과 후순으로 훑어보는 방법에 따라 왼쪽 노드를 창고에 넣고 2가 있는 노드의left를null로 설정하고 노드3가 창고에 나온 후에 2 노드의 좌우 서브 노드를 판단한다. 이때 왼쪽 노드가null인 것을 발견하면 이미 훑어봤다는 뜻이다. 그래서 value=2ans수조에 저장한 다음에 4가 있는 노드를 창고에 넣는다.그리고 4 다시 창고에 나가면 창고 꼭대기 원소가 2이고 이때 다시 좌우 노드를 판단한다. 왼쪽 노드가null인 것을 발견하고 왼쪽 노드가 두루 돌아다녔다고 생각하면 value=2ans 그룹에 다시 저장한다!여기를 보면 당신은 약간의 갈피를 잡을 수 있습니다. 우리는null로 노드가 옮겨갔다는 것을 나타낼 수 없고 정확한hash 방식을 사용해야 합니다. 여기는 elem.left=1elem의 왼쪽 노드가 옮겨갔다는 것을 나타냅니다. elem.left=0elem 노드가 있는 값이 ans수 그룹에 저장되었다는 것을 나타냅니다.

var inorderTraversal = function(root) {
  if (!root) return [];
  
  var stack = [], ans = [];

  stack.push(root);

  while (stack.length) {
    var elem = stack[stack.length - 1];

    if (elem.left === 1) {
      elem.left = 0;
      ans.push(elem.val);
    } else if (elem.left) {
      stack.push(elem.left);
      elem.left = 1;
    } else if (elem.left === null) {
      elem.left = 1;
    } else if (elem.right) {
      stack.push(elem.right);
      elem.right = null;
    } else {
      stack.pop();
    }
  }

  return ans;
};