sakura 技术分享 2022-06-15

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
};