DEV Community 👩‍💻👨‍💻

Cover image for 代码随想录day16 | 104. Maximum Depth of Binary Tree, 111.Minimum Depth of Binary Tree, 222.Count Complete Tree Nodes
Ming
Ming

Posted on • Updated on

代码随想录day16 | 104. Maximum Depth of Binary Tree, 111.Minimum Depth of Binary Tree, 222.Count Complete Tree Nodes

leetcode 104 - Maximum Depth of Binary Tree

给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。
for example, below tree maximum depth is 3.
Image description

这道题要重点掌握DFS-recursion-postorder的解法和BFS解法

一个node的depth(深度): 该节点到根节点root的距离,常使用pre_order
一个node的height(高度): 该节点到叶子结点的距离,常使用post_order
那么为什么这道题是来求depth深度,也能用post order解决呢?
就是因为这道题是求二叉树的最大深度,也就是根节点的高度.

solution 1.1:

// DFS:👍 Post order求跟节点高度

var maxDepth = function(root) {

   const helper = (node) => {
      if(!node) return 0;

      const leftTreeDepth = helper(node.left);
      const rightTreeDepth = helper(node.right)
      //当前父节点的高度 = 1 + 左/右子树的高度取大值 
      return 1 + Math.max(leftTreeDepth, rightTreeDepth)
   }

   return helper(root);
};

Enter fullscreen mode Exit fullscreen mode

solution 1.2

// DFS + backtracking:👍

var maxDepth = function (root) {
  if (!root) return 0;

  let maxDepth = -Infinity; //用来记录tree的最大深度

  //1.  确定递归的参数: tree node和 当前深度,不需要返回值了
  const helper = (node, curDepth) => {
    //2. 确定终止条件:碰到叶子节点,有必要时更新maxDepth
    if (!node.left && !node.right) {
      if (curDepth > maxDepth) maxDepth = curDepth;
    }
    //3. 确定单层递归逻辑:
    if (node.left) {
      //左
      curDepth++;
      helper(node.left, curDepth);
      curDepth--; // backtracking 回溯!!
    }
    if (node.right) {
      // 右
      curDepth++;
      helper(node.right, curDepth);
      curDepth--; // backtracking 回溯!!
    }
  };

  helper(root, 1);
  return maxDepth;
};

Enter fullscreen mode Exit fullscreen mode

solution 2:

// BFS: 👍

var maxDepth = function(root) {
   if(!root) return [];

    let queue = [root];
    let depth = 0;

    while(queue.length){
      let len = queue.length;
      depth++;

      for(let i=0; i<len; i++){
        let node = queue.shift();
        if(node.left) queue.push(node.left);
        if(node.right) queue.push(node.right);
      }

    }

    return depth;
};
Enter fullscreen mode Exit fullscreen mode

leetcode 111 - Minimum Depth of Binary Tree

给定一个二叉树,找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明: 叶子节点是指没有子节点的节点。
for example, 下面二叉树最小深度是2
Image description

这道题BFS和DFS_postorder解法都要掌握,但是注意DFS写起来容易掉进一个陷阱:处理左右孩子不为空的逻辑要写上

// DFS: 👍

var minDepth = function (root) {

  const getDepth = (node) => {
    if (!node) return 0; 

    let leftTreeDepth = getDepth(node.left); 
    let rightTreeDepth = getDepth(node.right); 

    /* 处理左右孩子不为空要注意: 😀 */

    //如果左子树为空,右子树不为空,说明最小深度是1+右子树的深度
    if (!node.left && node.right) return 1 + rightTreeDepth; 
    //右子树为空,左子树不为空,最小深度是1+左子树的深度
    if (node.left && !node.right) return 1 + leftTreeDepth;
    //左右子树都不为空,返回左右子树深度最小值+1
    return 1 + Math.min(leftTreeDepth, rightTreeDepth);
  };

  return getDepth(root);
};
Enter fullscreen mode Exit fullscreen mode
// BFS: 👍

var minDepth = function(root) {

  if(!root) return [];

    let queue = [root];
    let min_depth = 0;

    while(queue.length){
      let len = queue.length;
      min_depth ++;

      for(let i=0; i<len; i++){
        let node = queue.shift();
        // 😀(遇见的第一个leaf节点上),则该节点深度最小
        if(!node.left && !node.right) return min_depth
        if(node.left) queue.push(node.left);
        if(node.right) queue.push(node.right);
      }

    }

    return min_depth;

};
Enter fullscreen mode Exit fullscreen mode

leetcode 222 - Count Complete Tree Nodes

给出一个完全二叉树,求出该树的节点个数
Image description

//👍 solution1: BFS (就把root当成普通的二叉树)

var countNodes = function (root) {
  if (!root) return 0;

  // let visited = [];
  let queue = [root];
  let count = 0;

  while (queue.length) {
    let node = queue.shift();
    // visited.push(node.val);
    count++;
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return count; //return visited.length;
};
Enter fullscreen mode Exit fullscreen mode
//👍 solution 2: DFS遍历 (就把root当成普通的二叉树)

var countNodes = function (root) {
  let count = 0; // let visited = [];

  const helper = (node) => {
    if (!node) return;

    if (node.left) helper(node.left);
    if (node.right) helper(node.right);
    count++; // visited.push(node.val);
  };

  helper(root);
  return count; // return visited.length;
};
Enter fullscreen mode Exit fullscreen mode
//👍 solution 3: 利用complete binary tree特性

var countNodes = function (root) {
  // 确定终止条件
  if (!root) return 0;
  let left = root.left; let right = root.right;
  let leftDepth = 0; let rightDepth = 0;
  while (left) {
    left = left.left;
    leftDepth++;
  }
  while (right) {
    right = right.right;
    rightDepth++;
  }
  //确定终止条件, 如果当前的节点是一个满二叉树(full binary tree)则直接计算节点数不用非要遍历一遍
  if (leftDepth == rightDepth) return Math.pow(2, leftDepth + 1) - 1; // 一个满二叉树的节点数 = 2的深度次方-1

  // 单层递归逻辑:
  return countNodes(root.left) + countNodes(root.right) + 1;
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

DEV

Thank you.

 
Thanks for visiting DEV, we’ve worked really hard to cultivate this great community and would love to have you join us. If you’d like to create an account, you can sign up here.