fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
东哥带你刷二叉树（纲领篇） :: labuladong的算法小抄
你只需要思考每一个节点应该做什么，其他的不用你管，抛给二叉树遍历框架，递归会对所有节点做相同的操作。
遇到一道二叉树的题目时的通用思考过程是：是否可以通过遍历一遍二叉树得到答案？如果不能的话，是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案? 如果需要设计到子树信息, 建议使用后续遍历.
js 版二叉树直径：
var diameterOfBinaryTree = function(root) {
let maxDiameter = 0;
// 对每个节点计算直径，求最大直径
maxDepth(root);
return maxDiameter;
// 计算二叉树的最大深度
function maxDepth(root) {
if (root == null) {
return 0;
}
const leftMax = maxDepth(root.left);
const rightMax = maxDepth(root.right);
// 后序位置顺便计算最大直径
const myDiameter = leftMax + rightMax;
maxDiameter = Math.max(maxDiameter, myDiameter);
return Math.max(leftMax, rightMax) + 1;
}
};
二叉树的简单 js 实现，可以用来调试代码：
class TreeNode {
constructor(value) {
this.val = value;
this.left = null;
this.right = null;
}
insert(values) {
const queue = [this];
let i = 0;
while (queue.length > 0) {
let current = queue.shift();
for (let side of ["left", "right"]) {
if (!current[side]) {
if (values[i] !== null) {
current[side] = new TreeNode(values[i]);
}
i++;
if (i >= values.length) return this;
}
if (current[side]) queue.push(current[side]);
}
}
return this;
}
}
const tree = new TreeNode(15);
tree.insert([1, 2, 3, 4, 3, 8, 7, 5, 10, 12, 11, null, null, null]);
js 二叉树分治前序遍历
function preorderTraverse(root) {
const res = [];
if (root == null) {
return res;
}
// 前序遍历的结果，root.val 在第一个
res.push(root.val);
// 利用函数定义，后面接着左子树的前序遍历结果
res.push(...preorderTraverse(root.left));
// 利用函数定义，最后接着右子树的前序遍历结果
res.push(...preorderTraverse(root.right));
return res;
}
515 的题其实利用层序遍历有一种更通用的模板：
var largestValues = function(root) {
const level = []
const traverse = (root, depth) => {
if(!root) return
if(!level[depth]) level[depth] = []
traverse(root.left, depth+1)
level[depth].push(root.val)
traverse(root.right, depth+1)
}
traverse(root, 0)
const ans = level.map(arr => Math.max.apply(null, arr))
return ans
};
啊！突然懂了，左孩子已经执行了一次depth++，在离开结点之前，右孩子也进行了depth++，该层的depth加了两次，所以离开前要让depth自减一次以维护。
@cold-runner 这样理解好像不对，是因为当前节点存在，所以进入了当前节点深度++；退出节点时，因为是深度遍历，所以深度要--才能将深度维护正确。
@labuladong,求最大深度的第一种解法中
// 记录最大深度
int res = 0;
// 记录遍历到的节点的深度
int depth = 0;
// 主函数
int maxDepth(TreeNode root) {
traverse(root);
return res;
}
// 二叉树遍历框架
void traverse(TreeNode root) {
if (root == null) {
// 到达叶子节点，更新最大深度
res = Math.max(res, depth);
return;
}
// 前序位置
depth++;
traverse(root.left);
traverse(root.right);
// 后序位置
depth--;
}
res = Math.max(res, depth);这行代码，可以放到前序位置那里，即depth++后面。也可以得到答案，但这两种方式有什么大的区别吗？比如时间效率问题上。我用leetcode运行测试这两种写法执行时间都是显示0s通过。
// 定义：输入一棵二叉树的根节点，返回这棵树的前序遍历结果 List<Integer> preorderTraverse(TreeNode root) { List<Integer> res = new LinkedList<>(); if (root == null) { return res; } // 前序遍历的结果，root.val 在第一个 res.add(root.val); // 利用函数定义，后面接着左子树的前序遍历结果 res.addAll(preorderTraverse(root.left)); // 利用函数定义，最后接着右子树的前序遍历结果 res.addAll(preorderTraverse(root.right)); } 这个函数忘记写返回值了！！！ 应该在末尾加上 return res;
请问，力扣第 543 题「 二叉树的直径」中， 为什么是int myDiameter = leftMax + rightMax，而不是int myDiameter = leftMax + rightMax + 2?我理解这个直径还需要加上root到左子树的1和root到右子树的1。
