leetcode 104 - Maximum Depth of Binary Tree
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。
for example, below tree maximum depth is 3.
这道题要重点掌握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);
};
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
这道题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);
};
// 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;
};
Top comments (0)