94.二叉树的中序遍历
题目描述：给定一个二叉树，返回它的中序遍历
思路分析：二叉树的三种遍历，用递归写非常简单，不过一般面试都要求写非递归。
递归版本：
先序遍历
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
var result = [];
function pushRoot(node){
if(node != null){
result.push(node.val);
if(node.left != null){
pushRoot(node.left);
}
if(node.right != null){
pushRoot(node.right);
}
}
}
pushRoot(root);
return result;
};
中序遍历
**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
var result = [];
function pushRoot(root){
if(root != null){
if(root.left != null){
pushRoot(root.left);
}
result.push(root.val);
if(root.right !=null){
pushRoot(root.right);
}
}
}
pushRoot(root);
return result;
};
后序遍历
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function(root) {
var result = [];
function pushRoot(node){
if(node != null){
if(node.left != null){
pushRoot(node.left);
}
if(node.right != null){
pushRoot(node.right);
}
result.push(node.val);
}
}
pushRoot(root);
return result;
};
非递归版本：
- 使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
- 如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
- 如果遇到的节点为灰色，则将节点的值输出。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
const [WHITE, GRAY] = [0, 1]; // WHITE - 未访问的新结点； GRAY - 已访问的结点
const res = [];
const stack = [[WHITE, root]];
let color, node;
while (stack.length) {
[color, node] = stack.pop(); // 若栈中有元素，则按照左节点、根节点、右节点的顺序依次弹出元素
if (!node) continue;
if (color === WHITE) {
// 当前指向的结点是未访问过的结点，将其右节点，根节点，左节点依次入栈
stack.push([WHITE, node.right]);
stack.push([GRAY, node]);
stack.push([WHITE, node.left]);
} else res.push(node.val);
}
return res;
};
101.对称二叉树
题目描述：给定一个二叉树，检查它是否是镜像对称的。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
if (!root) return true;
return check(root.left, root.right);
function check(left, right) {
// 左右子树都不存在，是对称的
if (!left && !right) {
return true;
}
// 左右子树都存在，要继续判断
if (left && right) {
//左右子树的节点值要相等
// 左子树的left和右子树的right相等
// 左子树的right和右子树的left相等
return left.val === right.val &&
check(left.left, right.right) &&
check(left.right, right.left);
}
//左右子树中的一个不存在，一个存在，不是对称的
else {
return false;
}
}
};
226.翻转二叉树
题目描述：翻转一颗二叉树，使其对称。
var invertTree = function(root) {
if (root) {
let temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
}
return root;
};
104.二叉树的最大深度
题目描述：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
var maxDepth = function(root) {
if (!root) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};
543.二叉树的直径
题目描述：给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
思路分析：这道题是求二叉树深度的衍生体。某节点的直径为两边子树的高度之和。递归遍历这棵树，求以每一个节点为顶点的直径长度，每次总返回最大的那个路径。最终返回最大直径长度
var diameterOfBinaryTree = function(root) {
if (!root) return 0;
let temp = maxDepth(root.left) + maxDepth(root.right)
return Math.max(temp, diameterOfBinaryTree(root.left),
diameterOfBinaryTree(root.right));
function maxDepth(root) {
if (!root) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};
};
538.把二叉搜索树转换成累加树
题目描述：给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和
思路分析：注意二叉搜索树的特点，比某节点大的节点值都在右子树里，不断遍历右子树求和并更新节点即可。
var convertBST = function(root) {
let count = 0;
sum(root);
return root;
function sum(root) {
if (root) {
sum(root.right);
count += root.val;
root.val = count;
sum(root.left);
}
}
};
617.合并二叉树
题目描述：给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
var mergeTrees = function(t1, t2) {
if(!t1) return t2 //若t1节点为空，那直接返回t2节点，不管t2是否为空
if(!t2) return t1 //若t2为空，那肯定t1肯定不为空，返回t1节点
t1.val = t1.val + t2.val //能执行到这里证明t1与t2节点均不为空，那就两值相加，替换t1原来的值
t1.left = mergeTrees(t1.left, t2.left ) //递归遍历两者的左子树
t1.right = mergeTrees(t1.right, t2.right) ////递归遍历两者的右左子树
return t1 //t1必然是返回的根节点，为啥？因为都拼到t1树上了啊
};
114.二叉树展开为链表
题目描述：给定一个二叉树，原地将它展开为一个单链表。
image.png
思路分析：
题目本质就是把树的左子树全部并到右子树中，按照示例，就是前序了。也就是说，要把root的右子树，放到左子树的最后一个结点的右子树中。至于左右子树，各自的处理，就是标准的递归了。
所以递归函数的步骤可以理解如下：
- 当root为空时，不处理；
- 递归处理root的左子树；
- 当root有左子树时，要找到最后一个结点last，从root.left开始往下找，循环找right直到最后一个结点即可开始把左子树并入到右子树；
- 以上述方法递归处理root的右子树；
为将左子树并入到右子树，核心处理步骤如下：
- 将root的右子树移到last的右指针，last.right = root.right;
- root的左子树移到root的右指针:root.right = root.left;
- 清空root的左指针：root.left = null
var flatten = function(root) {
if (root === null) return null;
//先处理左子树
if (root.left) {
//循环找到左子树的最后一个节点
let last = root.left;
while (last.right) {
last = last.right;
}
//开始左子树的移动三连
last.right = root.right;
root.right = root.left;
root.left = null;
}
//递归处理右子树
flatten(root.right);
};
102.二叉树的层序遍历
题目描述：给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
image.png
var levelOrder = function(root) {
if(!root) return []
let queue = [root]
let res = []
while(queue.length){
let len = queue.length
let arr = []
for (let i = 0; i < len; i++) {
let node = queue.shift()
arr.push(node.val)
if(node.left) queue.push(node.left)
if(node.right) queue.push(node.right)
}
res.push(arr)
}
return res
};
199.二叉树的右视图
题目描述：给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
image.png
//思路类似于层序遍历二叉树，用一个队列来存储二叉树的节点
//用一个res数组存储每一层的最后一个节点值
var rightSideView = function(root) {
if (!root) return [];
const queue = [];
const res = [];
queue.push(root);
while (queue.length) {
let len = queue.length;
while (len) {
let node = queue.shift(); // 取出队列第一个元素
if(len === 1) res.push(node.val); // 当是 当前一层的最后一个元素时，把值加入arr
if(node.left) queue.push(node.left); // 继续往队列添加元素
if(node.right) queue.push(node.right);
len--;
}
}
return res;
};
