## DEV Community 👩‍💻👨‍💻

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.

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

``````

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

``````

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

## leetcode 111 - Minimum Depth of Binary Tree

for example， 下面二叉树最小深度是2

``````// 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);
};
``````
``````// 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;

};
``````

## leetcode 222 - Count Complete Tree Nodes

``````//👍 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;
};
``````
``````//👍 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;
};
``````
``````//👍 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;
};
``````

#### 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.