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

henu_Newxc03

发布于 2022-05-12 14:23:35

2410

发布于 2022-05-12 14:23:35

BM23 二叉树的前序遍历

/*
 * 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 二叉树的中序遍历

/*
 * 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 二叉树的后序遍历

/*
 * 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 求二叉树的层序遍历

/*
 * 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 按之字形顺序打印二叉树

/* 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 二叉树的最大深度

/*
 * 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 二叉树中和为某一值的路径(一)

/*
 * 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 二叉搜索树与双向链表

/* 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 对称的二叉树

/* 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 合并二叉树

/*
 * 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 二叉树的镜像

/*
 * 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 判断是不是二叉搜索树

/*
 * 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 判断是不是完全二叉树

/*
 * 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 判断是不是平衡二叉树

/* 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 二叉搜索树的最近公共祖先

/*
 * 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 在二叉树中找到两个节点的最近公共祖先

/*
 * 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 重建二叉树

/* 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 输出二叉树的右视图

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 求二叉树的右视图
 * @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
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-05-11，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

二叉树

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

二叉树

登录后参与评论

0 条评论

热度

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

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

BM23 二叉树的前序遍历

BM24 二叉树的中序遍历

BM25 二叉树的后序遍历

BM26 求二叉树的层序遍历

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

BM28 二叉树的最大深度

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

BM30 二叉搜索树与双向链表

BM31 对称的二叉树

BM32 合并二叉树

BM33 二叉树的镜像

BM34 判断是不是二叉搜索树

BM35 判断是不是完全二叉树

BM36 判断是不是平衡二叉树

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

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

BM40 重建二叉树

BM41 输出二叉树的右视图

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

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

BM23 二叉树的前序遍历

BM24 二叉树的中序遍历

BM25 二叉树的后序遍历

BM26 求二叉树的层序遍历

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

BM28 二叉树的最大深度

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

BM30 二叉搜索树与双向链表

BM31 对称的二叉树

BM32 合并二叉树

BM33 二叉树的镜像

BM34 判断是不是二叉搜索树

BM35 判断是不是完全二叉树

BM36 判断是不是平衡二叉树

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

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

BM40 重建二叉树

BM41 输出二叉树的右视图

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

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