트리의 기본은 traverse를 하면서
!root먼저 처리하고
return; = 위로 돌아가기

대칭확인

对称的二叉树
left, right이 둘 중하나만 있거나, 둘다 있는데 root.val이 다르면 대칭이아니다

function isSymmetrical(pRoot)
{
    if(!pRoot) return true; // 없어도 대칭

    function checkSym(left, right) {
        if(!left && !right) return true; // 자식이 없음 대칭
        else if(!left || !right) return false; // 자식이 하나만 있음 대칭아님
        else {
            if(left.val !== right.val) return false; // 둘다 자식이 있는데 값이 다름
            // 둘다 자식이 있는데 값이 같음. 계속 체크
            return checkSym(left.left, right.right) && checkSym(left.right, right.left);
        }
    }
    return checkSym(pRoot.left, pRoot.right);
}

merge 2 trees

合并二叉树

 // merge 합치기
function mergeTrees( t1 ,  t2 ) {
    if(!t1 && !t2) return null;
    if(!t1) return t2;
    if(!t2) return t1;

    t1.val += t2.val;
    t1.left = mergeTrees(t1.left, t2.left);
    t1.right = mergeTrees(t1.right, t2.right);

    return t1;
}

미러링

二叉树的镜像
새로운 포인터로 switch

function Mirror( pRoot ) {
    if(!pRoot) return null;

    let temp = pRoot.left;
    pRoot.left = Mirror(pRoot.right);
    pRoot.right = Mirror(temp);
    return pRoot;
}

binary search tree인지 판단

判断是不是二叉搜索树
binary tree != binary search tree
bst는 left, root, right 크기가 정렬이 된것.

처음시도

function isValidBST( root ) {
    if(!root) return true; // 없어도?

    function check(root) {
        if(!root) return true;
        if(!root.left && !root.right) return true; //
        // left > root || right < root이면 false
        if(root.left.val > root.val || root.right.val < root.val) return false;
        if(root.left.val < root.val && root.val < root.right.val) {
            return check(root.left) && check(root.right);
        }
    }
    return check(root);
}

위의 경우는 이어져있는 left, root, right만의 비교라 전체크기비교가 맞는지는 알지 못한다.

정답

{3,2,5,1,4} 같은 경우고려
한번에 모아놓고 크기비교
inorder = bst순서

function isValidBST( root ) {
    if(!root) return true; // 없어도?
    let res = [];
    
    function inorder(root) {
        if(!root) return; // res에 넣을 필요없다
        inorder(root.left);
        res.push(root.val);
        inorder(root.right);
    }
    inorder(root);

    for(let i = 0; i < res.length-1; i++) {
        if(res[i] >= res[i+1]) return false;
    }
    return true;
}

isCompleteTree

判断是不是完全二叉树
젤 깊은깊이의 노드들이 모두 왼쪽에 공백없이 모여있는 트리

전부 큐에 넣고 null이 나올때까지 pop
null이 나왔을때 큐의 길이가 존재 ? false : true

처음시도

right 스펠링 틀렸음

정답

function isCompleteTree( root ) {
    let queue = [];
    queue.push(root); // val을 집어넣지 않고 노드자체를 넣음
    let isEnd = false;

    while(queue.length) {
        let curr = queue.shift(); // arr.shift
        if(!curr) { // 계속 null이면 계속 isEnd=true, 더이상 큐에 push안 하고 while밖으로 나감
            isEnd = true;
        }
        else {
            if(isEnd && queue.length) {
                return false;
            };
            queue.push(curr.left);
            queue.push(curr.right);
        }
    }
    return true;
}

is balanced bst?

判断是不是平衡二叉树

• 대칭이 될 필요없다
• 층의 차이 <=1

생각
잎에서부터 깊이를 측정한다음 left, right의 max+1을 위로 넘겨준다.

처음시도

function IsBalanced_Solution(pRoot)
{
    if(!pRoot) return true;
    const left = getDepth(pRoot.left);
    const right = getDepth(pRoot.right);
    
    return left && right;
}

function getDepth(root) {
    if(!root) return 0;
    const left = getDepth(root.left);
    const right = getDepth(root.right);
    return Math.abs(left-right) <= 1 ? true : false;
}

input이 {1} 일때 true여야하는데 false가 나왔다.
0 && 0 = 0(false)
0과 false를 차별해야해야하므로 false를 0 대신 -1로 설정하자

• getDepth는 깊이를 반환하는데 차이가 1초과할때 -1을 반환하는거에 중점하자

정답

function IsBalanced_Solution(pRoot)
{
    if(!pRoot) return true;
    return getDepth(pRoot) > -1;
}

function getDepth(root) {
    if(!root) return 0;
    const left = getDepth(root.left);
    const right = getDepth(root.right);
    // 차이가 1초과 할때 || 자식 left or right이 -1일때
    if(Math.abs(left-right) > 1 || left === -1 || right === -1) return -1;
    return Math.max(left, right)+1;
}

BST의 가장 가까운 조상

二叉搜索树的最近公共祖先

bst는 배열이 되있으므로 node1 < root && root < node2인 root를 찾음된다.
p < root && root < q 혹은 p나 q 자체가 root일때 그 root를 리턴

function lowestCommonAncestor( root ,  p ,  q ) {
    // write code here
    if((p < root.val && root.val < q) || root.val === p || root.val === q) return root.val;
    if(q < root.val) {
        return lowestCommonAncestor(root.left, p, q); // return? 밑에서 리턴한걸 올라올라가서 끝에서 리턴
    }
    if(root.val < p) {
        return lowestCommonAncestor(root.right, p, q);
    }
}

BT에서 가까운 공통조상 찾기

在二叉树中找到两个节点的最近公共祖先

BST != BS

• 최소공통조상 조건 = 하나는 left, 하나는 right인 root (BST에선 한개만 조상보다 크거나 작을때)
• 예외는 만약 둘다 왼쪽이나 오른쪽에 있으면, 현재 노드의 밑에 노드들이 조상이다.
  ===== 생각 =====
• 타겟(left나 right)을 찾으면 타겟을 리턴한다 root.val === t1 || t2
• 못 찾으면 내려가서 계속 찾는다
• 현재노드의 left, right을 모두 찾으면 현재 노드를 리턴한다.

function lowestCommonAncestor( root ,  o1 ,  o2 ) {
    if(!root) return null;
    // write code here
    // 타겟을 찾았으면 타겟을 리턴한다
    if(root.val === o1 || root.val === o2) return root.val;
    // 못 찾았으면 계속 내려가서 찾는다
    let left = lowestCommonAncestor(root.left, o1, o2);
    let right = lowestCommonAncestor(root.right, o1, o2);

    // left, right 둘다 찾았다
    if(left && right) return root.val;

    // left만 찾았다
    if(left) return left;
    // right만 찾았다
    if(right) return right;
    // 둘다 못 찾았다
    return null;
}

pre, in으로 트리 만들기

重建二叉树

pre는 root순서대로
in은 오른쪽, root, 왼쪽 이렇게 나뉜다

• pre에서 root를 하나씩 뽑은뒤, in을 사용해 left, right을 나눈다.

주의할 점

• pre, in은 단순한 string[]으로, new 노드를 만들어줘야함
• [] 는 존재한다. 그러므로 빈 배열인지 판단하고 싶을땐 !arr가 아닌 !arr.length로 판단해야한다

const a = []; 
console.log(!a); // false
console.log(!a.length); // true

function reConstructBinaryTree(pre, vin)
{
    if(!pre.length || !vin.length) return null; // null, length
    let root = new TreeNode(pre.shift()); // new treenode
    let rootIdx = vin.indexOf(root.val); // val

    root.left = reConstructBinaryTree(pre, vin.slice(0, rootIdx));
    root.right = reConstructBinaryTree(pre, vin.slice(rootIdx+1));

    return root;
}

오른쪽 시야노드 찾기

输出二叉树的右视图

1. 먼저 정상 트리를 만든다
2. 층별로 나눈다
3. 층의 마지막 요소들을 리턴

function makeTree(xianxu ,  zhongxu) {
    if(!xianxu.length || !zhongxu.length) return null;
    let root = new TreeNode(xianxu.shift());
    let rootIdx = zhongxu.indexOf(root.val);

    root.left = makeTree(xianxu, zhongxu.slice(0, rootIdx));
    root.right = makeTree(xianxu, zhongxu.slice(rootIdx+1));

    return root;
}

function solve( xianxu ,  zhongxu ) {
    // write code here
    const tree = makeTree(xianxu, zhongxu);
    const levels = [];

    function getLevels(node, level) {
        if(!node) return; // 없으면 안 넣음 됨
        if(!levels[level]) {
            levels.push([]);
        }
        levels[level].push(node.val);
        getLevels(node.left, level+1);
        getLevels(node.right, level+1);
    }
    getLevels(tree, 0); // array index 0부터 시작

    return levels.map(l => l.pop());
}

레벨별로 노드출력하기

레벨순서 + left to right 니까 preorder로 traverse 하면서 노드의 값을 res에 넣는다.
새로운 레벨이면, 초기화시킨뒤 node.val값을 push하기
node가 존재하지않으면 넘어가기

var levelOrder = function (root) {
  if (!root) return [];
  const result = [];

  function preorder(node, level) {
    if (!node) return;
    if (!result[level]) {
      result.push([]);
    }
    result[level].push(node);
    preorder(node.left, level + 1);
    preorder(node.right, level + 1);
  }

  preorder(root, 0);
  return result;
};