javaScript 二叉树 若干算法题分析(上)

链、表、树、图……

树在算法领域,可谓独霸一方,与之相关的问题千奇百怪。二叉树又是其中的典范,能延伸到 堆、AVL树、SB树、红黑树等等结构。
走进这个世界,慢慢了解,你会收获到很多。本文先来一些简单的算法题,带你了解二叉树。

二叉树前序遍历(先序遍历)

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。数据范围:二叉树的节点数量满足0≤ n ≤100 ,二叉树节点的值满足1≤ val ≤100 ,树的各节点的值各不相同

思路: 根据递归的时机,可以很轻松知道 先序中序后序的切入点。

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
 }

function preOrder(arr, node) {
    if (!node) return null
    arr.push(node.val)  // 先序
    preOrder(arr, node.left)
    // 中序
    preOrder(arr, node.right)
    // 后序
}

/**
 * @param root TreeNode类 
 * @return int整型一维数组
 */
 function preorderTraversal( root ) {
    // write code here
    if (!root) return []
    let arr = []
    preOrder(arr, root)
    //console.log('arr-',arr)
    return arr
}
module.exports = {
    preorderTraversal : preorderTraversal
};

求二叉树的层序遍历

给定一个二叉树,返回该二叉树层序遍历的结果,(从左到右,一层一层地遍历)
例如:给定的二叉树是{3,9,20,#,#,15,7}, 该二叉树层序遍历的结果是 [ [3], [9, 20], [15, 7] ]

数据范围:二叉树的节点数满足 1≤ n ≤10^5

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
 }

function level(arr, node, L) {
    if (!node) return []
    // 每递归一层,就相当于进入下一层,就添加当前的节点
    if (!arr[L]) arr[L] = []
    arr[L].push(node.val)  
    
    level(arr, node.left, L+1)
    level(arr, node.right, L+1)
    
}
/**
  * @param root TreeNode类 
  * @return int整型二维数组
  */
 function levelOrder( root ) {
    // write code here
    // 从root,第0层起
    if(!root) return []
    let arr = []
    level(arr, root, 0)
    return arr
}
// 测试
let root = new TreeNode(3)
root.left = new TreeNode(9)
root.right = new TreeNode(20)
root.right.left =  new TreeNode(15)
root.right.right = new TreeNode(7)

console.log('arr-',levelOrder(root))

module.exports = {
    levelOrder : levelOrder
};

按之字形顺序打印二叉树

给定一个二叉树,返回该二叉树的之字形层序遍历,(第一层从左向右,下一层从右向左,一直这样交替)

数据范围:0≤n≤1500,树上每个节点的val满足 ∣ val ∣<=1500
要求:空间复杂度:O(n),时间复杂度:O(n)

思路:在层级遍历的思想下,再判断层级的奇偶,进行数组头添加还是尾添加即可。

function level(arr, node, L) {
    if (!node) return []
    if (!arr[L]) arr[L] = []
    // 偶数层级 尾添加, 奇数层级 头添加。从0层开始
    if (L % 2 === 0) {
         arr[L].push(node.val)  
    }else {
         arr[L].unshift(node.val)  
    }
    level(arr, node.left, L+1)
    level(arr, node.right, L+1)
}

function levelOrder( root ) {
    if(!root) return []
    let arr = []
    level(arr, root, 0)
    return arr
}
module.exports = {
    levelOrder : levelOrder
};

二叉树的最大深度

求给定二叉树的最大深度,深度是指树的根节点到任一叶子节点路径上节点的数量。

最大深度是所有叶子节点的深度的最大值。(注:叶子节点是指没有子节点的节点。)

数据范围:0≤n≤100000,树上每个节点的val满足 |val|<= 100
要求: 时间复杂度 O(n)

function level(arr, node, L) {
    if (!node) return L
    
    let ld = level(arr, node.left, L+1)
    let rd = level(arr, node.right, L+1)
    return Math.max(ld, rd)
}

function levelOrder( root ) {
    if(!root) return 0
    let height = level(arr, root, 0)
    return height
}
module.exports = {
    levelOrder : levelOrder
};

总结: 二叉树的套路就是 递归左右子节点,期间可以实现很多功能。
这篇是比较基础的一些算法题,下篇讲解稍微复杂的二叉树问题。

有问题反馈加微信:mue233 私聊送一本电子书,绝对受益良多! 微信公众号:慕意,分享创业、使用的软件和教程~
知识星球精选推荐 » javaScript 二叉树 若干算法题分析(上)