JS刷算法题：二叉树
Q1.翻转二叉树（easy）
如题所示
示例：
输入：
4
/
2 7
/ \ /
1 3 6 9
输出：
4
/
7 2
/ \ /
9 6 3 1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/invert-binary-tree</pre>
这道题目起源于一个非常搞笑的事件：据说大名鼎鼎的Mac软件包管理工具Homebrew的作者，因为做不出这道在leetcode上难度为easy的题，被谷歌公司拒了。。。
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
格式要求
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function(root) {
// 编码
};
分析：二叉树遍历
思路就是遍历二叉树的每一个节点，然后把左右链接替换一下就可以了。前序/中序/后序 都可以。如下所示
具体代码
var invertTree = function(root) {
traveral(root);
return root;
};
function traveral(node) {
if (node === null) return;
traveral(node.left);
traveral(node.right);
const temp = node.right;
node.right = node.left;
node.left = temp;
}
Q2.二叉树的右视图(middle)
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/ \
2 3 <---
\ \
5 4 <---
输入: [1,2,3,null,5,null,null]
输出: [1, 3, 5]
解释:
1 <---
/ \
2 3 <---
\
5 <---
格式要求
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var rightSideView = function(root) {
// 编码
}
分析：层序遍历
题目的思路很明显，对二叉树进行层序遍历，然后取得每一层的最后一个节点。放到一个数组里最后返回。
1.我们可以设置一个队列存放依次遍历的节点对象。
2.使用两层循环
- 内层循环 通过不断出队列的方式遍历当前层的节点，同时通过左右链接收集下一层节点
- 外层循环 判断队列长度>0时就继续运行，从而实现逐层迭代
3.在每次内层循环中获取最右端的非空节点
具体代码
var rightSideView = function(root) {
if (!root) return [];
const queue = [];
const arrRS = [];
// 先保存根结点，也就是第一层二叉树
queue.push(root);
while (queue.length > 0) {
// 将队列长度先保存到一个变量里面
// 表示的是上一层的节点的数量
let length = queue.length;
let temp = null;
// 遍历上一层节点，将它们的子节点加入队列中，收集得到二叉树的下一层
for (let i = 0; i < length; i++) {
// 出队列，并获得返回的父节点
const node = queue.shift();
// 每次都用当前节点的val覆盖temp
// temp最后会等于当前层最右的一个非空节点的val值
if (node.val) temp = node.val;
// 收集当前节点的左节点和右节点，从而得到下一层
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
// 收集每一层的最右节点
arrRS.push(temp);
}
return arrRS;
};
Q3.二叉树中的最大路径和(difficult)
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例1:
输入: [1,2,3]
1
/ \
2 3
输出: 6
示例2:
输入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出: 42
格式要求
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxPathSum = function(root) {
// 编码
};
思路分析
- 整体思路 ：通过后序遍历，自底向上计算。
image
因为后序遍历的计算过程是： 左节点-右节点-根结点。 所以通过这种遍历方式，我们可以在计算两个子节点的基础上，推断当这两个节点到父节点的最大路径和。然后不断向上累加，去计算最大值。
同时在每个节点都通过Math.max更新当前的最大值，直到回归到根结点的时候，也就能比较出最大值来了。
- 路径的单一性 ： 当一个节点是只是作为一个中间节点，而不是一个根节点的时候：左节点和右节点只能选择一个作为经过的路径。 因为路径是“单一”的而不是“分叉”的
例如下面的图示中， 当我们通过比较选择9-7-10这条的时候，节点8就不在路径内了
image
- 根节点的连接性： 当一个节点作为根节点的时候，它可以将两个子树的路径连接起来
image
4. 对于两个子节点的 累加值 A，B，分3种情况讨论
- A>0,B>0 : 选择Math.max(A,B)作为经过路径
- A>0,B<0 : 选择A作为经过路径
- A<0,B>0 : 选择B作为经过路径
- A<0,B<0 : A,B都不选
综上所述
我们的思路是：
- 后序遍历，自底向上计算
- 对于每个节点，假设它是根结点，计算它联合两个子树路径后的最大值
- 对于每个节点，假设它是中间节点，选择两条中较大的一条子树作为路径
- 对于2，3分上面的四种情况进行分别处理
具体代码
// 1.考虑全为负数的情况
// 2.考虑当前节点为负的情况
let max = Number.MIN_VALUE;
var maxPathSum = function(root) {
max = root.val;
traveral(root);
return max;
};
function traveral(node) {
if (node === null) return 0;
const a = traveral(node.left);
const b = traveral(node.right);
let v = node.val;
if (a >= 0 && b >= 0) {
max = Math.max(max, v + a + b);
v += Math.max(a, b);
} else if (a >= 0) {
max = Math.max(max, v + a);
v += a;
} else if (b >= 0) {
max = Math.max(max, v + b);
v += b;
}
return v;
}
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
本文完
