leetcode 문제 해결 기록(9)-중등

1. 두 갈래 검색 트리 검증

제목:
두 갈래 나무를 정해 효과적인 두 갈래 검색 나무인지 아닌지를 판단한다.
두 갈래 검색 트리에 다음과 같은 특징이 있다고 가정합니다.
노드의 왼쪽 트리는 현재 노드보다 작은 수만 포함합니다.노드의 오른쪽 하위 트리는 현재 노드보다 큰 수만 포함합니다.모든 왼쪽 나무와 오른쪽 나무 자체도 두 갈래로 나무를 수색해야 한다.
사고방식: 두 갈래 검색 나무의 특징은 왼쪽의 나무가 뿌리 노드보다 작고 오른쪽의 나무도 뿌리 노드보다 크며 매 과목의 나무도 귀속되어야 한다는 판단이다.따라서 하나의 변수로 현재 하위 트리의 최소값과 최대값을 기록하면 된다

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
  const isValidBSTAA = (root, min, max) => {
    if (!root) return true;
    if (root.val <= min || root.val >= max) return false;
    return (
      isValidBSTAA(root.left, min, root.val) &&
      isValidBSTAA(root.right, root.val, max)
    );
  };
  if (!root) return true;
  return isValidBSTAA(root, -Infinity, Infinity);
};

생각을 바꾸면 두 갈래 검색 트리의 중서 역력은 승서이다. 그러면 우리는 중서 역력의 방식으로 현재의 수와 앞의 수의 값을 비교하면 된다.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
  let pre = -Infinity;
  let flag = false;
  const search = (root) => {
    if (flag) return;
    if (!root) return;
    search(root.left);
    if (root.val <= pre) {
      flag = true;
      return;
    }
    pre = root.val;
    search(root.right);
  };
  search(root);
  return !flag;
};

2. 두 갈래 나무의 층계가 두루 다니다

제목: 두 갈래 나무를 드리겠습니다. 층차적으로 훑어보는 노드 값을 되돌려 주십시오.(즉, 왼쪽에서 오른쪽으로 모든 노드에 층층이 접근한다.)
사고방식: 이곳의 귀착은 교체보다 번거롭다
교체:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
  const res = [];
  if (!root) return res;
  const stack = [root];
  while (stack.length) {
    const temp = stack.map((item) => item.val);
    res.push(temp);
    const newStack = stack.reduce((res, item) => {
      if (item.left) res.push(item.left);
      if (item.right) res.push(item.right);
      return res;
    }, []);
    stack.splice(0, Infinity, ...newStack);
  }
  return res;
};

3. 두 갈래 나무의 톱니 층이 두루 흐르다

제목:
두 갈래 나무를 정해서 노드 값을 되돌려주는 톱날 모양의 차원을 두루 훑어본다.(즉, 먼저 왼쪽에서 오른쪽으로, 다시 오른쪽에서 왼쪽으로 다음 층을 훑어보며, 이와 같이 층과 층 사이를 교체하여 진행한다.)
예를 들어 두 갈래 나무[3,9,20,null,null,15,7],
3/\9 20/\15 7은 다음과 같이 앤티앨리어싱 계층을 반복합니다.
[ [3], [20,9], [15,7] ]
사고방식: 프로그램과 유사하게 변수로 방향을 기록하면 된다

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
  if (!root) return [];
  const stack = [root];
  let flag = true;
  const res = [];
  while (stack.length) {
    const tempStack = [];
    const temp = stack.reduce((res, item) => {
      if (flag) {
        res.push(item.val);
      } else {
        res.unshift(item.val);
      }
      if (item.left) {
        tempStack.push(item.left);
      }
      if (item.right) {
        tempStack.push(item.right);
      }
      return res
    }, []);
    res.push(temp);
    flag = !flag;
        stack.splice(0, Infinity, ...tempStack);
  }
  return res;
};

4. 앞 순서와 중간 순서를 두루 훑어본 결과 두 갈래 나무 구조

제목:
한 그루의 나무의 전차적 역류와 중차적 역류에 따라 두 갈래 나무를 구성한다.
주의: 트리에 중복된 요소가 없다고 가정할 수 있습니다.
예를 들어
앞의 순서 반복preorder =[3,9,20,15,7]의 순서 반복inorder =[9,3,15,20,7]은 다음과 같은 두 갈래 나무로 되돌아옵니다.
3 /\ 9 20 / \ 15 7

사고방식: 앞의 첫 번째 노드가 뿌리 노드라는 것을 알 수 있다. 그래서 우리는 뿌리 노드가 중간 노드에 있는 하표를 찾으면 왼쪽의 노드가 서브 나무를 구성하고 오른쪽의 노드가 오른쪽 나무를 구성한다.그리고 하위 트리의 루트 노드는 앞의 루트에서 현재 루트 노드 + 현재 하위 트리의 노드 수량이며, 좌우의 하위 트리의 수량은 중간 루트의 아래 표에서 알 수 있습니다.그래서 귀속 처리하면 돼요.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = (preorder, inorder) => {
  return helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1)
}

function helper(preorder, p_start, p_end, inorder, i_start, i_end) {
  if (p_start > p_end) return null 
  let rootVal = preorder[p_start] 
  let root = new TreeNode(rootVal) 
  let mid = inorder.indexOf(rootVal) 
  let leftNum = mid - i_start 

  root.left = helper(preorder, p_start + 1, p_start + leftNum, inorder, i_start, mid - 1)
  root.right = helper(preorder, p_start + leftNum + 1, p_end, inorder, mid + 1, i_end)
  return root
}

5. 중차순과 후차순을 반복하여 두 갈래 나무를 구성한다

제목:
한 그루의 나무의 중차 역류와 후차 역류에 따라 두 갈래 나무를 구성한다.
주의: 트리에 중복된 요소가 없다고 가정할 수 있습니다.
예를 들어
inorder = [9,3,15,20,7] 후서적postorder = [9,15,7,20,3]은 다음과 같은 두 갈래 트리를 되돌려줍니다.
3 /\ 9 20 / \ 15 7
사고방식: 앞의 문제와 유사하게 뒷차례가 흐르는 마지막 노드는 뿌리 노드이다. 뿌리 노드가 중간차례가 흐르는 결과의 위치에 따라 우리는 좌우 나무의 수량을 계산한 다음에 좌우 나무의 뿌리 노드가 뒷차례가 흐르는 결과의 위치를 계산하고 귀속 처리한다