二叉树的前序遍历

  1. var preorderTraversal = function(root) {
  2. let result=[]
  3. const pre=(node)=>{
  4.     if(!node)
  5.         return []
  6.      result.push(node.val)
  7.      pre(node.left)
  8.      pre(node.right)
  9.  }
  10.  pre(root)
  11.  return result
  12. };

二叉树的后序遍历

var postorderTraversal = function(root) {
let result=[]
const after=(node)=>{
    if(!node)
        return []
    after(node.left)
    after(node.right)
    result.push(node.val)
}
after(root)
return result
};

二叉树的中序遍历

var inorderTraversal = function(root) {
let result=new Array()
const middleNode=(root)=>{
        if(!root){
            return []
        }

        middleNode(root.left)
        result.push(root.val)
        middleNode(root.right)
    }
    middleNode(root)
    return result
};

不同的二叉搜索树

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
 let G=new Array(n+1).fill(0)
 G[0]=1
 G[1]=1
   for (let i = 2; i <= n; ++i) {
        for (let j = 1; j <= i; ++j) {
            G[i] += G[j - 1] * G[i - j];
        }
        }
    return G[n]
};

平衡二叉树

var isBalanced = function(root) {
if(root===null)return true
else{
    return Math.abs(height(root.left)-height(root.right))<=1&&isBalanced(root.left)&&isBalanced(root.right)
}
};
const height=(root)=>{
if(root===null) return 0
else return Math.max(height(root.left),height(root.right))+1
}

二叉搜索树的第k大节点

var kthLargest = function(root, k) {
let res=null
const remiddle=(root)=>{
    if(!root){
        return null
    }

    remiddle(root.right)
    k--
    if(!k) res=root.val
    remiddle(root.left)

}
remiddle(root)
return res
};

二叉树的层序遍历

var levelOrder = function(root) {
   let result=[]
   let queue=[]
   if(!root) return result
   queue.push(root)
   while(queue.length){
       let length=queue.length
       let subres=[]
       for(let i=0;i<length;i++){
           let node=queue.shift()
           subres.push(node.val)
           if(node.left) queue.push(node.left)
             if(node.right) queue.push(node.right)
       }
       result.push(subres)

   }
   return result
};

二叉树的深度

const height=(root)=>{
if(root===null) return 0
else return Math.max(height(root.left),height(root.right))+1
}

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

function hasPathSum( root ,  sum ) {
    // write code here
    if(!root) return false
    if(!root.left&&!root.right&&sum-root.val===0)
        return true
    return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val)
}
module.exports = {
    hasPathSum : hasPathSum
};

验证二叉搜索树

var isValidBST = function(root) {
let key=-Infinity 
const middleNode=(root)=>{
        if(!root){
            return true
        }
        let l=middleNode(root.left)
        if(root.val<=key) return false
        key=root.val
        let r=middleNode(root.right)
       return l && r
    }
   return middleNode(root)
};

判断是不是完全二叉树

function isCompleteTree( root ) {
    let queue=[]
    let stop=false
    queue.push(root)
    while(queue.length){
        let node=queue.shift()
        if(!node){
            stop=true
        }else{
            if(queue.length&&stop) return false
            queue.push(node.left)
            queue.push(node.right)
        }
    }
    return true
}

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

function lowestCommonAncestor(root,p,q) {
   if(root==null) return -1
    if((p>=root.val&&q<=root.val)||(p<=root.val&&q>=root.val))
        return root.val
    else if(p<=root.val&&q<=root.val)
        return lowestCommonAncestor(root.left,p,q)
    else
        return lowestCommonAncestor(root.right,p,q)
}
module.exports = {
    lowestCommonAncestor : lowestCommonAncestor
};

二叉树的最近公共祖先

function lowestCommonAncestor( root ,  o1 ,  o2 ) {
    // write code here
     const helper= (root, p, q) => {
        if (root == null || root.val == o1 || root.val == o2)
         return root;
        const left = helper(root.left, o1, o2);
        const right = helper(root.right, o1, o2);
        //如果left为空，说明这两个节点在root结点的右子树上，我们只需要返回右子树查找的结果即可
            if (left == null)
                return right;
            //同上
            if (right == null)
                return left;
            //如果left和right都不为空，说明这两个节点一个在root的左子树上一个在root的右子树上，
            //我们只需要返回cur结点即可。
            return root;
    }
    return helper(root, o1, o2).val;
}

重建二叉树

function reConstructBinaryTree(pre, vin)
{
    // write code here
    if(!pre.length||!vin.length) return null
    let root=pre[0]
    let i=vin.indexOf(root)
    const node={
        val:root,
        left:reConstructBinaryTree(pre.slice(1,i+1), vin.slice(0,i)
    ),
        right:reConstructBinaryTree(pre.slice(i+1),vin.slice(i+1))
    }
    return node
}
module.exports = {
    reConstructBinaryTree : reConstructBinaryTree
};

输出二叉树的右视图

function solve( xianxu , zhongxu ) {
    // write code here
const constructor=(xianxu , zhongxu)=>{
    if(!xianxu.length||!zhongxu.length){
        return null
    }
    let root=xianxu[0]
    let i=zhongxu.indexOf(root)
    const node={
        val:root,
        left:constructor(xianxu.slice(1,i+1),zhongxu.slice(0,i)),
        right:constructor(xianxu.slice(i+1),zhongxu.slice(i+1)),
    }
    return node
}
const root=constructor(xianxu , zhongxu)
if(!root) return[]
let queue=[]
let res=[]
queue.push(root)
while(queue.length){
    let len=queue.length
    let subres=[]
    for(let i=0;i<len;i++){
        let node=queue.shift()
        subres.unshift(node.val)
        if(node.left) queue.push(node.left)
        if(node.right) queue.push(node.right)
    }
    res.push(subres[0])
}
    return res
}
module.exports = {
    solve : solve
};

二叉搜索树与双向链表

function Convert(pRootOfTree)
{
   let head=null
    let pre=null
    function dfs(cur){
        if(cur===null) return 
        dfs(cur.left)
        if(pre===null){
            head=cur
        }else{
            pre.right=cur
        }
        cur.left=pre
        pre=cur
        dfs(cur.right)
    }
    dfs(pRootOfTree)
    return head
}

对称的二叉树

function isSymmetrical(pRoot)
{
    const isSame=(left,right)=>{
        if(!left&&!right) return true
        if(left==null||right==null||left.val!==right.val) return false
        return  isSame(left.left,right.right)&&isSame(left.right,right.left)
    }
    // write code here
    return isSame(pRoot,pRoot)
}

合并二叉树

function mergeTrees( t1 ,  t2 ) {
    // write code here
    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
}

二叉树的镜像

function Mirror( pRoot ) {
    // write code here
    if(!pRoot) return null
    let temp= pRoot.left
    let left=Mirror( pRoot.left )
    let right=Mirror( pRoot.right )
    pRoot.left=right
    pRoot.right=left
    return pRoot
}

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

9181652975913_.pic.jpg

var pathSum = function(root, target) {
    let res=[]
    let path=[]
    const recur=(node,tar)=>{
        if(!node) return 
        path.push(node.val)
        tar=tar-node.val
        if(!node.left&&!node.right&&tar===0){
            res.push(path.slice(0))
        }
        recur(node.left,tar)
        recur(node.right,tar)
        path.pop()

    }
    recur(root,target)
    return res
};