剑指offer Binary Tree Breadth-First Search Depth-First Search

剑指offer-二叉树的深度

Posted by franki on May 17, 2021

二叉树的深度

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：

给定二叉树 [3,9,20,null,null,15,7]，

示例

  3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

思路

方案一：dfs 利用后序遍历，每次获取当前节点的深度，当叶子节点为空时，返回0，求得了左子树和右子树的深度的情况下，用Math.max(root.left.deep, root.right.deep)+1，得到树最终的深度。

方案二：bfs 每遍历一层，计数器+1，直到遍历完成，则可得到树的深度

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
// 方案一：dfs
var maxDepth = function(root) {
    if (root === null) {
        return 0;
    }
    return dfs(root);
};

let max = 1;
function dfs(root, k=1) {
    if (root === null) {
        return 0;
    }
    return Math.max(dfs(root.left), dfs(root.right)) + 1;    
}

// 方案二：bfs
var maxDepth = function(root) {
    if (root === null) {
        return 0;
    }
    let queue = [root];
    let res = 0;

    while (queue.length) {
        // 每一层节点的暂存区域
        const tmp = [];
        // 遍历每一层的节点
        for (let node of queue) {
            if (node.left) tmp.push(node.left);
            if (node.right) tmp.push(node.right);
        }
        // 重新赋值quue
        queue = tmp;
        // 深度+1
        res++;
    }
    return res;
};

复杂度分析:

方案一:

  • 时间复杂度: O(N)
  • 空间复杂度：O(N)

方案二:

  • 时间复杂度: O(N)
  • 空间复杂度：O(N)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG 科学上网 工具
    FRIENDS