目录
DFS 深序优先遍历
前序遍历递归
ts
function preOrder(root: TreeNode | null) {
let result: number[] = [];
if (root) {
result.push(root.val);
result = result.concat(preOrder(root.left));
result = result.concat(preOrder(root.right));
}
return result;
}中序遍历递归
ts
function inOrder(root: TreeNode | null) {
let result: number[] = [];
if (root) {
result = result.concat(inOrder(root.left));
result.push(root.val);
result = result.concat(inOrder(root.right));
}
return result;
}后序遍历递归
ts
function postOrder(root: TreeNode | null) {
let result: number[] = [];
if (root) {
result = result.concat(postOrder(root.left));
result = result.concat(postOrder(root.right));
result.push(root.val);
}
return result;
}WARNING
前序遍历、中序遍历、后序遍历 非递归 的实现起来略麻烦，也没啥实际作用，有兴趣可查询其他资料。
BFS 广度优先遍历
ts
function bfs(root: TreeNode | null): number[][] {
let result: number[][] = [];
const stack: TreeNode[] = [];
(root !== null) && stack.push(root);
while(stack.length) {
let len = stack.length;
const row: number[] = [];
while(len--) {
const leaf = stack.shift();
if (leaf) {
row.push(leaf?.val);
leaf.left && stack.push(leaf.left);
leaf.right && stack.push(leaf.right);
}
}
result.push(row);
}
return result;
}94.二叉树的中序遍历
题目描述
ts
给定一个二叉树的根节点 root ，返回它的中序遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]代码
ts
function inorderTraversal(root: TreeNode | null): number[] {
const result: number[] = [];
function inorder(leaf: TreeNode | null) {
if (leaf === null) return;
inorder(leaf.left);
result.push(leaf.val);
inorder(leaf.right);
}
inorder(root);
return result;
};102. 二叉树的层序遍历
题目描述
ts
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]代码
ts
function levelOrder(root: TreeNode | null): number[][] {
if (root === null) return [];
const result: number[][] = [];
const stack: TreeNode[] = [root];
while(stack.length) {
const row: number[] = [];
let rowLen = stack.length;
while(rowLen--) {
const leaf = stack.shift();
if (!leaf) continue;
row.push(leaf.val);
leaf.left && stack.push(leaf.left)
leaf.right && stack.push(leaf.right)
}
result.push(row);
}
return result;
};107. 二叉树的层序遍历 II
题目描述
ts
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]代码
ts
function levelOrderBottom(root: TreeNode | null): number[][] {
if (root === null) return [];
const stack: TreeNode[] = [root];
const result: number[][] = [];
while(stack.length) {
let len = stack.length;
const row: number[] = [];
while(len--) {
const leaf = stack.shift();
if (leaf) {
row.push(leaf.val);
leaf.left && stack.push(leaf.left);
leaf.right && stack.push(leaf.right);
}
}
result.unshift(row);
}
return result;
};104.二叉树的最大深度
题目描述
ts
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：
输入：root = [1,null,2]
输出：2代码
ts
function maxDepth(root: TreeNode | null): number {
if (root === null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};110.平衡二叉树
题目描述
ts
给定一个二叉树，判断它是否是平衡二叉树。
平衡二叉树是指该树所有节点的左右子树的深度相差不超过 1。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：
输入：root = []
输出：true代码
ts
function isBalanced(root: TreeNode | null): boolean {
return maxDepth(root) !== -1;
}
function maxDepth(root: TreeNode | null): number {
if (root === null) return 0;
const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);
if (
leftDepth === -1 || rightDepth === -1
|| leftDepth - rightDepth > 1 || rightDepth - leftDepth > 1
) {
return -1;
}
return Math.max(leftDepth, rightDepth) + 1
}ts
function isBalanced(root: TreeNode | null): boolean {
if (root === null) return true;
const leftDepth = depth(root.left);
const rightDepth = depth(root.right);
return Math.abs(leftDepth - rightDepth) <= 1
&& isBalanced(root.left)
&& isBalanced(root.right)
};
function depth(root: TreeNode | null): number {
if (root === null) return 0;
return Math.max(depth(root.left), depth(root.right)) + 1;
}98.验证二叉搜索树
题目描述
ts
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
- 节点的左子树只包含小于 当前节点的数。
- 节点的右子树只包含大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]
输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。代码
ts
function isValidBST(root: TreeNode | null): boolean {
const order = preOrder(root);
if (!order.length) return true;
for (let i = 1; i < order.length; i++) {
if (order[i] <= order[i - 1]) return false;
}
return true;
};
function preOrder(root: TreeNode | null): number[] {
let result: number[] = [];
if (root) {
result = result.concat(preOrder(root.left));
result.push(root.val);
result = result.concat(preOrder(root.right));
}
return result;
}