二叉树不是树

2020-09-12
二叉树不是树

大学老师在现在人的印象中，应该很多人连老师大号都不知道，更别说小号了，可是我大学数据结构老师，不管怎么忘记，我都会记得她说过的一句化，那就是“二叉树不是树”；如果再结合下面这张照片，就会觉得更有一丝好笑的气氛。
最终二叉树和树在数据结构里的差别如下：
二叉树算法模版

好了，言归正传，今天要说的是二叉树在算法中的应用，和之前的回溯算法模版一样，这次准备说一下二叉树的相关算法模版。
二叉树的遍历

在数据结构总，二叉树的组成有根节点、左子树、右子树，依据根节点不同的次序，二叉树的遍历方法有三种，分别是前序、中序、后序。
// 下面是leetcode上的题目与js答案
// 前序
var orderTraversal = function(root) {
    const res = [];
    traversal(root);
    function traversal (root) {
        if (root !== null) {
            res.push(root.val)    // 访问根节点的值
            traversal(root.left)  // 递归遍历左子树
            traversal(root.right) // 递归遍历右子树
        }
    }
    return res;
}
// 中序
var orderTraversal = function(root) {
    const res = [];
    traversal(root);
    function traversal (root) {
        if (root !== null) {
            traversal(root.left)  // 递归遍历左子树
            res.push(root.val)    // 访问根节点的值
            traversal(root.right) // 递归遍历右子树
        }
    }
    return res;
}
// 后序
var orderTraversal = function(root) {
    const res = [];
    traversal(root);
    function traversal (root) {
        if (root !== null) {
            traversal(root.left)  // 递归遍历左子树
            traversal(root.right) // 递归遍历右子树
            res.push(root.val)    // 访问根节点的值
        }
    }
    return res;
}
// 二叉树的其他演变
// leetcode 100 比较两颗二叉树是否相同
function compare(root1 , root2){
    // 两颗树都为空，相同
    if(root1 === null && root2 === null)return true;
    // 只有一颗树为空，不相同
    else if(root1 === null || root2 === null)return false;
    // 两颗树都不为空，比较值，并且递归比较子树
    else{
        return root1.val === root2.val && compare(root1;left , root2.left) && compare(root1.right , root2.right);
    }
}
// leetcode 226 翻转二叉树
function invertTree(root){
    if(!root)return null;
    [root.left , root.right] = [invertTree(root.right) , invertTree(root.left)];
    return root;
}
// leetcode 590 N叉树的后序遍历
var postorder = function(root) {
    let res = [];
    traversal(root);
    function traversal(root){
        if(!root)return null;
        root.children.forEach(e=>{
            traversal(e);
        });
        res.push(root.val);
    }
    return res;
}
// 如果递归方法已经腻了，我们可以用迭代来试试
var postorder = function(root) {
    let res = [];
    let tmp = [root];
    while(tmp.length){
        let now = tmp.shift();
        res.push(now.val);
        for (let i = now.children.length - 1; i >= 0; i--) {
            tmp.push(cur.children[i])
        }
    }
    return res;
}
// leetcode 102 二叉树的层序遍历 参照下面103
// leetcode 103 二叉树的锯齿形层次遍历 大白话：骚猪蛇皮走位，hhh
var zigzagLevelOrder = function(root) {
    if(root === null)return [];
    let res = [];
    travesal(root , 0);
    function travesal(node , depth){
        if(!root) return [];
        if(!res[depth]) res[depth] = [];
        // 此处不需要考虑 push 和 traversal递归 的顺序
        res[depth].push(node.val);
        // 此处全部都当作正常的从做到右遍历即可
        traversal(root.left , depth+1);
        traversal(root.right , depth+1);
    }
    // 对1，3，5。。。进行翻转，骚猪pdd的蛇皮走位大功告成
    res.forEach((e , i)=>{
        if(i%2 === 1){
            e = e.reverse();
        }
    });
    return res;
}
// leetcode 104 二叉树的最大深度 同上
// leetcode 107 二叉树的层次遍历 II 同上，最后reverse一下即可
// leetcode 199 二叉树的右视图(和层序遍历一样，最终将每层最右边的值取出即可)
var zigzagLevelOrder = function(root) {
    if(root === null)return [];
    let res = [];
    travesal(root , 0);
    function travesal(node , depth){
        if(!root) return [];
        if(!res[depth]) res[depth] = [];
        // 此处不需要考虑 push 和 traversal递归 的顺序
        res[depth].push(node.val);
        // 此处全部都当作正常的从做到右遍历即可
        traversal(root.left , depth+1);
        traversal(root.right , depth+1);
    }
    // 每层取最右边值
    let result = [];
    res.forEach(e=>{
        result.push(e.pop());
    });
    return res;
}
// leetcode 230 二叉搜索树中第K小的元素 (左子树小于根节点小于右子树，所以只要中序遍历，然后找到第k个元素即可)
var kthSmallest = function (root, k) {
    let arr = [];
    function travesal(node){
        // 找到第k个即可停止遍历
        if(node === null || arr.length >= k)return;
        travesal(node.left);
        arr.push(node.val);
        travesal(node.right);
    }
    return arr[k-1];
}
// 进一步优化, 使用O(1)的额外空间
var kthSmallest = function (root, k) {
    // res用来记录值，count来记录顺序，当达到k个时就立即停止，减少空间复杂度
    let res;
    let count = 0;
    function traversal(node) {
        if (node === null)return;
        if (count < k) {
            traversal(node.left);
        }
        if (++count === k) {
            res = node.val;
        }
        if (count < k) {
            traversal(node.right);
        }
    }
  traversal(root);
  return res;
}
// 102 二叉树的层序遍历
var levelOrder = function(root) {
    if(!root)return [];
    let res = [];
    traversal(root , 0);
    function traversal(root , depth){
        if(!root)return [];
        if(!res[depth]){
            res[depth] = [];
        }
        res[depth].push(root.val);
        traversal(root.left , depth+1);
        traversal(root.right , depth+1);
    }
    return res;
}
// 671 二叉树中第二小的节点
var findSecondMinimumValue = function(root) {
    if(!root) return -1;
    let res = [];
    traversal(root);
    function traversal(node){
        if(!node)return;
        traversal(node.left);
        res.push(node.val);
        traversal(node.right);
    }
    return res[1] === undefined ? -1 : res[1];
}
// leetcode 538/1038 把二叉搜索树转换为累加树
var convertBST = function(root) {
    if(!node)return root;
    let sum = 0;
    traversal(root);
    function traversal(node){
        if(node){
            traversal(node.right);
            sum += node.val;
            node.val = sum;
            traversal(node.left);
        }
    }
    return root;
}
// leetcode 700 二叉搜索树中的搜索
var searchBST = function(root, val) {
    function traversal (root) {
        if (!root) return null; 
        if(!root) return null;
        if(root.val === val) return root;
        if(root.val > val) return traversal(root.left);
        if(root.val < val) return traversal(root.right);
    }
  return traversal(root);
}
// leetcode 559 N叉树的最大深度
var maxDepth = function(root) {
    if(!root) return 0;
    let dep = 1;
    traversal(root , 1);
    function traversal(node , depth){
        if(node){
            dep = Math.max(dep , depth);
            node.children.forEach(e=>{
                traversal(e , depth+1);
            });
        }
    }
    return dep;
}
// leetcode 589 N叉树的前序遍历
var preorder = function(root) {
    if(!root)return root;
    let res = [];
    traversal(root);
    function traversal(node){
        if(node !== null){
            res.push(node.val);
            node.children.forEach(e=>{
                traversal(e);
            });
        }
    }
    return res;
}
// leetcode 897 递增顺序查找树
var increasingBST = function(root) {
  const arr = []
  function traversal (root) {
    if (root !== null) {
      traversal(root.left)
      arr.push(root.val)
      traversal(root.right)
    }
  }
  traversal(root)
  const res = new TreeNode(arr[0])
  let currentNode = res
  for (let i = 0; i < arr.length - 1; i++) {
    currentNode.left = null
    currentNode.right = new TreeNode(arr[i + 1])
    currentNode = currentNode.right
  }
  return res
}