JavaScript算法题总结 （三）二叉树

2022-05-12 14:23:35 浏览数 (1)

BM23 二叉树的前序遍历

代码语言：javascript复制
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型一维数组
 */
function preorderTraversal( root ) {
    // write code here
    let arr=[];
    function preOrder(root){
        if(!root) return null;
        arr.push(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }
    preOrder(root)
    return arr;
}
module.exports = {
    preorderTraversal : preorderTraversal
};

BM24 二叉树的中序遍历

代码语言：javascript复制
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型一维数组
 */
function inorderTraversal( root ) {
    // write code here
    let arr=[];
    function midOrder(root){
        if(!root) return;
        midOrder(root.left);
        arr.push(root.val);
        midOrder(root.right);
    }
    midOrder(root);
    return arr;
}
module.exports = {
    inorderTraversal : inorderTraversal
};

BM25 二叉树的后序遍历

代码语言：javascript复制
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型一维数组
 */
function postorderTraversal( root ) {
    // write code here
    let arr=[];
    function lastOrder(root){
        if(!root) return ;
        lastOrder(root.left);
        lastOrder(root.right);
        arr.push(root.val)
    }
    lastOrder(root)
    return arr;
}
module.exports = {
    postorderTraversal : postorderTraversal
};

BM26 求二叉树的层序遍历

代码语言：javascript复制
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
  * 
  * @param root TreeNode类 
  * @return int整型二维数组
  */
function levelOrder( root ) {
    // write code here
    let arr=[];
    function cxOrder(root,level){
        if(!root) return;
        if(!arr[level]) arr[level]=[];
        arr[level].push(root.val);
        cxOrder(root.left,level 1);
        cxOrder(root.right,level 1);
    }
    cxOrder(root,0)
    return arr;
}
module.exports = {
    levelOrder : levelOrder
};

BM27 按之字形顺序打印二叉树

代码语言：javascript复制
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function Print(pRoot)
{
    // write code here
    let arr=[];
    function cxOrder(root,level){
        if(!root) return;
        if(!arr[level]) arr[level]=[];
        arr[level].push(root.val);
        cxOrder(root.left,level 1);
        cxOrder(root.right,level 1);
    }
    cxOrder(pRoot,0);
    for(let i=0;i<arr.length;i  ){
        if(i%2!==0){
            arr[i].reverse();
        }
    }
    return arr
}
module.exports = {
    Print : Print
};

BM28 二叉树的最大深度

代码语言：javascript复制
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
  * 
  * @param root TreeNode类 
  * @return int整型
  */
function maxDepth( root ) {
    // write code here
    function dfs(root){
        if(!root) return 0;
        let left=dfs(root.left);
        let right=dfs(root.right);
        return Math.max(left 1,right 1);
    }
    return dfs(root);
}
module.exports = {
    maxDepth : maxDepth
};

BM29 二叉树中和为某一值的路径(一)

代码语言：javascript复制
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
  * 
  * @param root TreeNode类 
  * @param sum int整型 
  * @return bool布尔型
  */
function hasPathSum( root ,  sum ) {
    // write code here
    if(!root) return false;
    if(root.val===sum&&!root.left&&!root.right) return true;
    return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val)
}
module.exports = {
    hasPathSum : hasPathSum
};

BM30 二叉搜索树与双向链表

代码语言：javascript复制
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function Convert(pRootOfTree)
{
    // write code here
    let head=null,pre=null;
    function midOrder(cur){
        if(!cur) return;
        midOrder(cur.left);
        //递归到最左初始化头节点
        if(pre===null){
            head=cur;
        }else{
            pre.right=cur;
        }
        cur.left=pre;
        pre=cur;
        
        midOrder(cur.right);
    }
    midOrder(pRootOfTree);
    return head;
}
module.exports = {
    Convert : Convert
};

BM31 对称的二叉树

代码语言：javascript复制
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function isSymmetrical(pRoot)
{
    // write code here
    if(pRoot===null) return true;
    function compare(node1,node2){
        if(!node1&&!node2) return true;
        if(!node1||!node2)return false;
        if(node1.val!==node2.val) return false;
       return compare(node1.left,node2.right)&&compare(node1.right,node2.left)
    }
    return compare(pRoot.left,pRoot.right);
}
module.exports = {
    isSymmetrical : isSymmetrical
};

BM32 合并二叉树

代码语言：javascript复制
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
 * 
 * @param t1 TreeNode类 
 * @param t2 TreeNode类 
 * @return TreeNode类
 */
function mergeTrees( t1 ,  t2 ) {
    // write code here
    if(t1&&t2){
        t1.val =t2.val;
        t1.left=mergeTrees(t1.left,t2.left);
        t1.right=mergeTrees(t1.right,t2.right);
    }
    return t1||t2;
}
module.exports = {
    mergeTrees : mergeTrees
};

BM33 二叉树的镜像

代码语言：javascript复制
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pRoot TreeNode类 
 * @return TreeNode类
 */
function Mirror( pRoot ) {
    // write code here
    if(!pRoot) return;
    let t=pRoot.right;
    pRoot.right=Mirror(pRoot.left);
    pRoot.left=Mirror(t);
    return pRoot;
}
module.exports = {
    Mirror : Mirror
};

BM34 判断是不是二叉搜索树

代码语言：javascript复制
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return bool布尔型
 */
function isValidBST( root ) {
    // write code here
    let arr=[];
    function midOrder(root){
        if(!root) return;
        midOrder(root.left);
        arr.push(root.val);
        midOrder(root.right);
    }
    midOrder(root);
    for(let i=0;i<arr.length-1;i  ){
        if(arr[i]>arr[i 1])
            return false;
    }
    return true
}
module.exports = {
    isValidBST : isValidBST
};

BM35 判断是不是完全二叉树

代码语言：javascript复制
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return bool布尔型
 */
function isCompleteTree( root ) {
    // write code here
    let arr=[];
    arr.push(root);
    let end=false;
    while(arr.length){
        let node=arr.shift();
        if(!node) end=true;
        else{
            //如果已经碰到一次空了 arr还有长度 
            if(arr.length&&end) return false
            arr.push(node.left);
            arr.push(node.right);
        }
    }
    return true;
}
module.exports = {
    isCompleteTree : isCompleteTree
};

BM36 判断是不是平衡二叉树

代码语言：javascript复制
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function IsBalanced_Solution(pRoot)
{
    // write code here
    if(pRoot===null) return true;
    //判断左右子树的深度差值
    if(Math.abs(depth(pRoot.left)-depth(pRoot.right))>1) return false;
    //递归判断左右子树是否为平衡二叉树
    return IsBalanced_Solution(pRoot.left)&&IsBalanced_Solution(pRoot.right)
}
function depth(node){
    if(node===null){return 0};
    let left=depth(node.left);
    let right=depth(node.right);
    return Math.max(left,right) 1
}
module.exports = {
    IsBalanced_Solution : IsBalanced_Solution
};

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

代码语言：javascript复制
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }　
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @param p int整型 
 * @param q int整型 
 * @return int整型
 */
function lowestCommonAncestor( root ,  p ,  q ) {
    // write code here
    if(!root) return null;
        //如果俩值都小于根节点，说明祖先在左子树一侧
    if(p<root.val&&q<root.val)
        return lowestCommonAncestor(root.left,p,q);
        //如果俩值都大于根节点，说明祖先在右子树一侧
    else if(p>root.val&&q>root.val)
        return lowestCommonAncestor(root.right,p,q);
        //否则，在两个值中间，或者等于其中的一个值
    else
        return root.val;
}
module.exports = {
    lowestCommonAncestor : lowestCommonAncestor
};

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

代码语言：javascript复制
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
 * 
 * @param root TreeNode类 
 * @param o1 int整型 
 * @param o2 int整型 
 * @return int整型
 */
function lowestCommonAncestor( root ,  o1 ,  o2 ) {
    // write code here
    if(!root) return null;
    //如果p或q为根节点，则p或q为最近公共祖先
    if(root.val===o1||root.val===o2) return root.val;
    //在左子树寻找q和p的最近公共祖先
    let left=lowestCommonAncestor(root.left,o1,o2);
    //在右子树寻找q和p的最近公共祖先
    let right=lowestCommonAncestor(root.right,o1,o2);
    //如果p和q分属两侧，则根节点为最近公共祖先
    if(left!==null&&right!==null) return root.val;
    //如果左子树有值，则最近公共祖先在左子树，否则，在有子树
    return left!==null?left:right;
    
}

module.exports = {
    lowestCommonAncestor : lowestCommonAncestor
};

BM40 重建二叉树

代码语言：javascript复制
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
    // write code here
    if(!pre.length||!vin.length){
        return null;
    }
    let root=new TreeNode(pre.shift());
    let index=vin.indexOf(root.val);
    
    root.left=reConstructBinaryTree(pre, vin.slice(0,index));
    root.right=reConstructBinaryTree(pre, vin.slice(index 1,vin.length));
    
    return root;
}
module.exports = {
    reConstructBinaryTree : reConstructBinaryTree
};

BM41 输出二叉树的右视图

代码语言：javascript复制
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 求二叉树的右视图
 * @param xianxu int整型一维数组 先序遍历
 * @param zhongxu int整型一维数组 中序遍历
 * @return int整型一维数组
 */
function solve( xianxu ,  zhongxu ) {
    let level = 0; //表示树的深度
    let res = [];
    function rebuild(xianxu, zhongxu, level, res) {
        if(xianxu.length === 0) return null;
        const root = xianxu[0];
        const index = zhongxu.findIndex(node => node === root)
        //左子树的先序遍历结果
        const leftNodePreOrder = xianxu.slice(1, index   1);
        //左子树的中序遍历结果
        const leftNodeInOrder = zhongxu.slice(0, index);
        //右子树的先序遍历结果
        const rightNodePreOrder = xianxu.slice(index   1);
        //右子树的中序遍历结果
        const rightNodeInOrder = zhongxu.slice(index   1);
        
        rebuild(leftNodePreOrder, leftNodeInOrder, level   1, res);
        rebuild(rightNodePreOrder, rightNodeInOrder, level   1, res);
        
        //记录下每一层的
        res[level] = root;
    }
    
    rebuild(xianxu, zhongxu, level, res);
    
    return res;
}
module.exports = {
    solve : solve
};
编程算法 二叉树

0 人点赞