重拾数据结构与算法

A9ia

发布于：2023年2月17日

二叉树

二叉树遍历

前序：根节点 => 左子树 => 右子树
中序：左子树 => 根节点 => 右子树
后序：左子树 => 右子树 => 根节点
层序：按照每层的节点进行遍历
通过遍历序列获取树结构：前、后、层序都能确定顶部节点，中序能够根据顶部节点确定左右子树，所以通过遍历序列获取树结构时必须要有前、后、层三者之一，以及中序序列

// 前序、中序、后序遍历，调整内部函数的递归顺序即可。示例为后序
function orderTraversal( root ) {
    // write code here
    let result = []
    function traversal(node){
        if(node == null) return
        traversal(node.left)
        traversal(node.right)
        result.push(node.val)
    }
    afterTraversal(root)
    return result
}
// 层级遍历
function levelOrder(root) {
    let result = [];
    let dfs = (root, index) => {
        if (!root) {
            return;
        }
        if (!result[index]) {
            result[index] = [];
        }
        result[index].push(root.val);
        dfs(root.left, index + 1);
        dfs(root.right, index + 1);
    };
    dfs(root, 0);
    return result;
}
// 序列化二叉树
function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
function Serialize(pRoot, arr = []) {
    // write code here
    if (!pRoot) {
        arr.push("#");
        return arr;
    } else {
        arr.push(pRoot.val);
        Serialize(pRoot.left, arr);
        Serialize(pRoot.right, arr);
    }
    return arr;
}
function Deserialize(s) {
    // write code here
    let arr = 
    let a = arr.shift();
    let node = null;
    if (typeof a === "number") {
        node = new TreeNode(a);
        node.left = Deserialize(arr);
        node.right = Deserialize(arr);
    }
    return node;
}
module.exports = {
    Serialize: Serialize,
    Deserialize: Deserialize,
};

二叉树的操作也是基于上述遍历进行运算。

二叉搜索树转双向链表

// 利用栈，非常巧妙的完成了较小节点的暂存
function Convert(pRootOfTree)
{
    // write code here
     
    if(!pRootOfTree) return null
    let stack = [],p = pRootOfTree,pre = null,isFirst = true
    while(p||stack.length>0){
        while(p){
            stack.push(p)
            p = p.left
        }
        p = stack.pop()
        if(isFirst){
            pRootOfTree = p
            pre = pRootOfTree
            isFirst = false
        }else{
            pre.right = p
            p.left = pre
            pre = p
        }
        p = p.right
    }
    return pRootOfTree
}

二叉树的特殊类型

二叉搜索树：左侧子树的值都小于根节点的值，右侧子树的值都大于根节点的值

完全二叉树：除二叉树叶子节点层，所有层都没有空缺节点，且叶子节点从左到右连续没有空缺

平衡二叉树：是空树或者左右子树的高度差绝对值不超过1，且左右子树都是平衡二叉树

// 判断二叉搜索树
const helper = (root, lower, upper) => {
    if (root === null) {
        return true;
    }
    if (root.val <= lower || root.val >= upper) {
        return false;
    }
    return helper(root.left, lower, root.val) && helper(root.right, root.val, upper);
}
var isValidBST = function(root) {
    return helper(root, -Infinity, Infinity);
};

// 判断完全二叉树
function isCompleteTree( root ) {
    // write code here
    if(root == null) return true;
 
    const queue = [];
    queue.push(root);
 
    let flag = false;
    while(queue.length) {
        const node = queue.shift();
        if(node == null) {
            flag = true;
            continue;
        }
 
        if(flag == true) {
            return false;
        }
 
        queue.push(node.left);
        queue.push(node.right);
    }
    return true;
}
// 判断平衡二叉树
function IsBalanced_Solution(pRoot)
{
    if(!pRoot) return true;
    // write code here
    return (Math.abs(getMaxDepth(pRoot.left) - getMaxDepth(pRoot.right)) <=1) && IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right)
}
 
function getMaxDepth(root) {
    if(!root) return 0;
    return Math.max(getMaxDepth(root.left)+1,getMaxDepth(root.right)+1)
}