发布时间：2023-05-10 09:30
本系列所有文章都将会收录到GitHub中统一收藏与管理，欢迎ISSUE和Star。
GitHub传送门：Kiner算法算题记
本文属于系列文章《你真的了解二叉树吗》的第二部分——手撕算法篇。如果你还没有看过第一部分你真的了解二叉树吗（树形结构基础篇）的话，强烈建议先看一下第一部分的内容，这样你在解题时会更加如虎添翼。很多第一篇里面已经讲过的内容，在这里将不再赘述。
如果你有看过我上一篇文章你真的了解二叉树吗（树形结构基础篇）的话，应该已经知道了，我们树的遍历天生就适合使用递归实现，此外，还讲了如何设计和实现一个递归函数，如果对着两点不太了解或没看过上一篇文章的同学，请先移步你真的了解二叉树吗（树形结构基础篇）补一下基础先，这里就不赘述了，直接讲思路吧：
首先，先设计一下我们的递归函数
/*
* @lc app=leetcode.cn id=144 lang=typescript
*
* [144] 二叉树的前序遍历
*/
// @lc code=start
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function preorderTraversal(root: TreeNode | null, arr: number[]=[]): number[] {
// 判断边界条件
if(root) {
// 因为是前序遍历，所以先将根节点加入数组
arr.push(root.val);
// 递归遍历左子树和右子树
preorderTraversal(root.left, arr);
preorderTraversal(root.right, arr);
}
return arr;
};
// @lc code=end
以上是常规的递归方式实现，我们也可以使用迭代的方式实现
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
// 用一个栈辅助完成迭代遍历
const stack = [];
// 结果数组
const res = [];
// 当前节点
let cur = root;
// 如果当前节点为空或者栈为空时结束循环
while(cur || stack.length>0) {
while(cur) {
// 因为是前序遍历，所以根节点先存放到结果数组
res.push(cur.val);
// 为了在我们走到左子树的底部时，能够回到根节点继续遍历右子树，因此，先将根节点存入栈中
stack.push(cur);
// 继续遍历左子树，直到遍历到叶子节点
cur = cur.left;
}
// 左子树遍历完了，我们需要遍历右子树了，首先我们先要从栈顶把最近的一个根节点弹出
cur = stack.pop();
// 遍历弹出的这个根节点的右子树
cur = cur.right;
}
return res;
};
解题思路起始跟二叉树的解题思路一模一样，这里就不再赘述了。
首先，先设计一下我们的递归函数
/*
* @lc app=leetcode.cn id=589 lang=typescript
*
* [589] N 叉树的前序遍历
*/
// @lc code=start
/**
* Definition for node.
* class Node {
* val: number
* children: Node[]
* constructor(val?: number) {
* this.val = (val===undefined ? 0 : val)
* this.children = []
* }
* }
*/
function preorder(root: Node | null, arr: number[] = []): number[] {
// 边界条件
if(!root) return arr;
// 前序遍历，先将根节点放入结果数组
arr.push(root.val);
// 循环递归调用所有的子节点
root.children.forEach(child => {
preorder(child, arr);
});
return arr;
};
// @lc code=end
我们要反转一个二叉树，就要先将这个二叉树的左子树的子树和右子树的子树先反转，然后再反转根节点的左右子树。这里利用到了js中的解构赋值的新特性进行高效快速反转。
首先，先设计一下我们的递归函数
/*
* @lc app=leetcode.cn id=226 lang=typescript
*
* [226] 翻转二叉树
*/
// @lc code=start
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function invertTree(root: TreeNode | null): TreeNode | null {
// 边界条件，当root为空时直接返回
if(!root) return root;
// 先交换root的左右子树，这里我们利用js的解构赋值的新特性可以迅速的交换左右子树
[root.left, root.right] = [root.right, root.left];
// 分别递归左右子树
invertTree(root.left)
invertTree(root.right)
return root;
};
// @lc code=end
这道题其实就是我们二叉树的层序遍历，将每一层的节点依次输出。这里可以使用一个技巧，增加一个变量k代表当前遍历到二叉树的第几层，默认为0，即默认是二叉树的第一层
首先，先设计一下我们的递归函数
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function levelOrder(root: TreeNode | null,k=0, res: number[][] = []): number[][] {
// 边界条件，当root不存在时，直接返回结果数组
if(!root) return res;
// 如果结果数组的长度为k,说明我们准备遍历新的一层，但这层还没有数组来存放数据，所以要新建一个数组放到结果数组末尾
if(res.length===k) res.push([]);
// 将根节点的值放到第k位的数组中
res[k].push(root.val);
// 递归遍历左子树、右子树
levelOrder(root.left, k+1, res);
levelOrder(root.right, k+1, res);
return res;
};
我们二叉树层序遍历的实现不仅可以使用递归，使用队列+迭代的方式也可以实现，思路也都差不多
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function levelOrder(root: TreeNode | null, res: number[][]=[]): number[][] {
// 边界条件，root不存在是直接返回空数组
if(!root) return res;
// 用一个队列来存储节点，初始时根节点入队
const queue: TreeNode[] = [root];
// 用于记录当前遍历到了第几层
let k = 0;
while(queue.length!==0) {
// 当层数与结果数组长度一致时，说明遍历到了下一层，但没有一个数组用来存放下一层的数据，因此在结果数组最后放一个空数组
if(k===res.length) res.push([]);
// 将队列中的所有节点依次弹出，此时，队列中的所有节点都是当前层的节点，并且是从左到右排列的
let queueLen = queue.length;
// 注意，我们这行的终止条件是针对于本次循环的队列长度，如果在循环过程中动态加入队列中的元素，是不会循环到的，因此，可以在循环过程中
// 不断的将有子节点的元素的子节点压入队列而不用担心把下一层的数据也在本行输出
while(queueLen--) {
// 当根节点出队并将结果压入到第k层的数组中
const item = queue.shift();
res[k].push(item.val);
// 如果左子树存在则左子树入队
item.left && queue.push(item.left);
// 右子树存在，则右子树入队
item.right && queue.push(item.right);
}
// 本层所有节点处理完后，记得层数加一，准备遍历下一层
k++;
}
return res;
};
这道题起始跟上一道题没什么区别，仅仅是将上一道题的结果数组反转，这个在js中实现极其简单，就不再赘述了。
/*
* @lc app=leetcode.cn id=107 lang=typescript
*
* [107] 二叉树的层序遍历 II
*/
// @lc code=start
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function _lavelOrder(root: TreeNode|null, k: number, arr: number[][] = []): number[][] {
if(!root) return arr;
if(arr.length===k) arr.push([]);
arr[k].push(root.val);
_lavelOrder(root.left, k+1, arr);
_lavelOrder(root.right, k+1, arr);
return arr;
}
function levelOrderBottom(root: TreeNode | null): number[][] {
const res = _lavelOrder(root, 0);
// 使用双指针方式交换反转数组
for(let i=0,j=res.length-1;i<j;i++,j--) {
[res[i], res[j]] = [res[j], res[i]];
}
return res;
// 也可以直接使用数组自带的反转方法
// return res.reverse();
};
// @lc code=end
这一题其实是上面两题思路的综合，我们只需要先按照正常的层序遍历输出得到结果数组，然后将结果数组中的奇数行进行翻转就可以了。当然，我们可以用更好的方法，就是在进行层序遍历时，直接判断当前的层数k是奇数还是偶数，如果是奇数就往数组前面添加元素，否则往数组后面添加元素，这样就不需要额外再反转数组了
/*
* @lc app=leetcode.cn id=103 lang=typescript
*
* [103] 二叉树的锯齿形层序遍历
*/
// @lc code=start
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
// 方案一：先正常层序遍历，然后将奇数行数组反转
// function _zigzagLevelOrder(root: TreeNode | null, k:number=0, res: number[][]=[]): number[][] {
// if(!root) return res;
// if(k===res.length) res.push([]);
// res[k].push(root.val);
// _zigzagLevelOrder(root.left, k + 1, res);
// _zigzagLevelOrder(root.right, k + 1, res);
// return res;
// };
// function zigzagLevelOrder(root: TreeNode | null): number[][] {
// const res = _zigzagLevelOrder(root);
// // 将奇数行反转
// return res.map((item, index) => {
// if(index&1) {
// item = item.reverse();
// }
// return item;
// })
// }
// 方案二：在进行层序遍历时，如果k是奇数，则从数组前面开始添加元素，否则从后面添加元素
function _zigzagLevelOrder(root: TreeNode | null, k:number=0, res: number[][]=[]): number[][] {
if(!root) return res;
if(k===res.length) res.push([]);
(k&1)?res[k].unshift(root.val):res[k].push(root.val);
_zigzagLevelOrder(root.left, k + 1, res);
_zigzagLevelOrder(root.right, k + 1, res);
return res;
};
function zigzagLevelOrder(root: TreeNode | null): number[][] {
return _zigzagLevelOrder(root);
}
// @lc code=end
概念：对于任意一个子树而言，他的左右子树的高度差的绝对值不超过1的树被称为平衡二叉树
那么，依照题意，我们能想到的就是计算一棵树的左右子树的树高，然后看看他们差绝对值是否大于1，为了仅使用一次递归就判断出这棵树是否是平衡树，我们可以在计算树高的时候，假设如果这棵树不是平衡树，也就是说左右子树树高差的绝对值是大于1的时候，我们就直接返回一个负数，如-1，这样，当我们的程序执行完后，只要判断树高是否小于0就可以知道当前的树是否是平衡树了。
首先，先设计一下我们的递归函数
/*
* @lc app=leetcode.cn id=110 lang=typescript
*
* [110] 平衡二叉树
*/
// @lc code=start
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function getHeight(root: TreeNode | null): number {
// 边界条件，如果根节点为空，则树高0
if(!root) return 0;
// 分别计算左右子树的树高
const lH = getHeight(root.left);
const rH = getHeight(root.right);
// 假设：如果当前root的左右子树不平衡，则返回一个负数，如-1
// 除此之外，因为是递归程序，如果左右子树的子树的高小于0，那就说明他们的子树已经不平衡了，无需继续递归，直接返回-1
if(Math.abs(lH-rH)>1 || lH < 0 || rH < 0) return -1;
// 一个树的树高，应该是左右子树的树高最大值加一
return Math.max(lH, rH) + 1;
}
function isBalanced(root: TreeNode | null): boolean {
// 只要树高大于等于0，说明这颗树是平衡的
return getHeight(root) >= 0;
};
// @lc code=end
这道题的解题思路其实就是在我们不断往下找的时候，都把targetNum与当前的节点的值计算出一个差值，作为下一次递归时的targetNum，这样，当我们找到叶子节点的时候，只要叶子节点端的值等于targetNum的话，就说明存在这条路径了。
首先，先设计一下我们的递归函数
/*
* @lc app=leetcode.cn id=112 lang=typescript
*
* [112] 路径总和
*/
// @lc code=start
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
// 边界条件，如果root为空时，直接返回false
if(!root) return false;
// 如果当前节点是叶子节点，那么这个节点的值必须等于targetSum
if(!root.left && !root.right) return root.val === targetSum;
// 在左子树中查找是否有满足条件的路径
if(root.left && hasPathSum(root.left, targetSum - root.val)) return true;
// 在右子树中查找是否有满足条件的路径
if(root.right && hasPathSum(root.right, targetSum - root.val)) return true;
// 都不满足则返回false
return false;
};
// @lc code=end
如果有看过我写的上一篇文章你真的了解二叉树吗（树形结构基础篇）的同学应该是不会陌生了，上一篇文章中，已经带着大家在思维逻辑层面上分析过这题的解题思路了，但是没有一起编码实现，现在来还债了。
再来回顾一下大概的思路吧：
# 前序遍历输出结果
<1> 5 2 3 4
# 中序遍历输出结果
5 <1> 3 2 4
# 我们知道前序遍历的第一位就是我们二叉树的根节点，那么，我们根据这个根节点的数值在中序遍历中找到1所在的位置
# 这样，我们就知道，5是左子树，3 2 4是1的右子树序列，左子树无需继续处理，右子树可以直接递归处理得到最终的结果
/*
* @lc app=leetcode.cn id=105 lang=typescript
*
* [105] 从前序与中序遍历序列构造二叉树
*/
// @lc code=start
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
if(preorder.length===0) return null;
// 用于记录根节点在中序遍历中的位置
let pos = 0;
// 找到根节点在中序遍历序列中的位置
while(inorder[pos] !== preorder[0]) ++pos;
// 分别用来存储拆分后的左右子树的前序和中序遍历序列
let l_pre = [], l_in = [], r_pre=[],r_in=[];
// 将左子树的前序遍历序列和中序遍历序列存起来
for(let i=0;i<pos;i++) {
l_pre.push(preorder[i+1]);
l_in.push(inorder[i]);
}
// 将右子树的前序遍历和中序遍历的序列存起来
for(let i=pos+1;i<preorder.length;i++) {
r_pre.push(preorder[i]);
r_in.push(inorder[i]);
}
// 构建二叉树
const node = new TreeNode(preorder[0], buildTree(l_pre, l_in), buildTree(r_pre, r_in));
return node;
};
// @lc code=end
这道题就是让我们算一下一棵树有几个节点，我们只要知道这样的一个公式：总结点数量=左子树节点数量+右子树节点数量+根节点数量（1）即可
/*
* @lc app=leetcode.cn id=222 lang=typescript
*
* [222] 完全二叉树的节点个数
*/
// @lc code=start
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function countNodes(root: TreeNode | null): number {
// 边界条件，如果root不存在，则返回0
if(!root) return 0;
return countNodes(root.left) + countNodes(root.right) + 1;
};
// @lc code=end
二叉搜索树：右子树上所有的值都会大于根节点的值，左子树上的所有节点都会小于根节点的值。所以，二叉搜索树的中序遍历输出一定是一个有序数组。
由于这是一颗二叉搜索树，那么左子树的树肯定小于根节点，右子树肯定大于根节点
从这个特性我们就可以得出：
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
// 计算节点数量
function getCount(root: TreeNode): number {
if(!root) return 0;
return getCount(root.left) + getCount(root.right) + 1;
}
// 由于这是一颗二叉搜索树，那么左子树的树肯定小于根节点，右子树肯定大于根节点
// 从这个特性我们就可以得出：
// 如果要找第k大的树，并且k小于或者等于右子树节点数量的话，那我们可以先到右子树中去查找，
// 如果k等于右子树节点数量加1，那么说明我们要找的数其实就是根节点
// 如果不是上述两种情况，那么，我们就直接在左子树中查找，不过此时，因为我们已经排除了根节点和右子树了，就不再是找左子树第k大的节点了，我们应该减去根节点和右子树节点的数量
function kthLargest(root: TreeNode | null, k: number): number {
// 获取右子树节点数量
const count_r = getCount(root.right);
// 如果k小于等于右子树节点数量，则在右子树上查找第k大的树
if(k<=count_r) return kthLargest(root.right, k);
// 如果k等于右子树节点数量加1，说明要找的树就是根节点
if(k===count_r+1) return root.val;
// 否则去左子树查找第k-(count_r+1)=k- count_r - 1 大的数
return kthLargest(root.left, k - count_r - 1);
};
这道题我们其实就是在边界条件处理好之后，看一下B能否匹配一整颗A树，如果不能匹配，那么就看你一下B能不能匹配A的左子树或者其右子树，如果能够匹配上任意一个，就说明B是A的子结构
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
// 递归匹配子树结构
function isMatch(a: TreeNode, b: TreeNode) {
// 如果b为空，肯定匹配，返回true
if(!b) return true;
// 如果a为空则不可能匹配，返回false
if(!a) return false;
// 如果a和b的值不一致，返回false
if(a.val !== b.val) return false;
// 分别递归匹配a、b的左子树和右子树
return isMatch(a.left, b.left) && isMatch(a.right, b.right);
}
function isSubStructure(A: TreeNode | null, B: TreeNode | null): boolean {
// 依据题意，如果B为空，则不是任何树的子结构，直接返回false
if(!B) return false;
// 若A为空，B不为空，则不可能匹配上，返回false
if(!A) return false;
// 递归判断A、B是否能够匹配，如果匹配上了，则返回true
if(isMatch(A, B)) return true;
// 上面的情况都不是，那么就分别去A的左子树和右子树看一下能否匹配，只要二者有一个匹配就算匹配成功
return isSubStructure(A.left, B) || isSubStructure(A.right, B);
};
这道题在实现上确实是有一定的难度，我们可以借助上一篇文章你真的了解二叉树吗（树形结构基础篇）中讲过的完全二叉树的编号方式以及一个队列来辅助我们完成这个题目。在完全二叉树的编号中，假如当前节点的编号为i，那么他的左子树的编号为2*i，右子树的编号为2*i+1，不过这题中，有可能会因为编号过大导致整形数据溢出的情况，所以我们需要特殊处理。具体的解题思路，代码注释写得很清楚，直接看代码吧。
/*
* @lc app=leetcode.cn id=662 lang=typescript
*
* [662] 二叉树最大宽度
*/
// @lc code=start
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
// 为了方便存储节点和它对应编号，定义一个包装类
class Wrapper {
constructor(public node: TreeNode, public idx: number){
}
}
function widthOfBinaryTree(root: TreeNode | null): number {
// 用来存储结果
let res = 0;
// 定义一个包装类的队列，这个包装类可以存储节点和他对应的编号
const queue: Wrapper[] = [];
// 先将根节点和他的编号0加入队列
queue.push(new Wrapper(root, 0));
// 用于存储每一层有多少个节点
let rowSize;
while(rowSize = queue.length) {
// 设置当前层最小编号和最大编号的初始值都为父节点的编号
let lIdx = queue[0].idx, rIdx = queue[0].idx;
// 遍历当前层的每一个元素
while(rowSize--) {
// 先将队首元素出队
const { node, idx } = queue.shift();
// 当前层最大编号为父节点的编号
rIdx = idx;
// 当存在左子树时，使用左子树根节点和其对应的编号创建包装类，并加入到队列
// 其实这里，最难的就是这个编号如何界定。
// 我们有学过完全二叉树的编号方式，可以参考这种编号方式，
// 第i个节点的做子树根节点的编号为2*i,右子树的编号为2*i+1
// 所以，到了这里，我们就直接使用idx * 2和idx * 2 + 1代表左子树和右子树编号
// 如果我们这么提交的话，会遇到一个问题，就是当我们的树的节点足够大时，这个编号会超出
// 我们整数的范围，那么，我们要怎样在不影响程序运行结果的前提下，缩减这个编号，避免整数溢出呢
// 我们来想想，对于一个编号来说，其实最小和最大编号分别为6和7，其实跟为0和1是没有本质上的区别的
// 因为我们拿这个编号并没有实质的作用，只是为了用这个编号计算差值，7-6的差值跟1-0的差值是一样的
// 所以，我们这边直接让当前的编号鉴于父节点的最小编号lIdx，以此来缩减编号大小
node.left && queue.push(new Wrapper(node.left, (idx - lIdx) * 2));
node.right && queue.push(new Wrapper(node.right, (idx - lIdx) * 2 + 1));
}
// 一层循环结束后，我们只要计算上一个宽度，与当前层最大编号减去最小编号加1，然后两者取最大值找到最大宽即可
// 例如：当前层最小和最大的编号是：0和8,那么这一层其实有8-0+1=9个节点空间，也就是宽度为9.
res = Math.max(res, rIdx - lIdx + 1);
}
return res;
};
// @lc code=end