节点的结构如下,以力扣为标准
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)
}
}
前序遍历
递归
const preorderTraversal = (root: TreeNode | null): number[] => {
if (root == null) return []
return [root.val, ...preorderTraversal(root.left), ...preorderTraversal(root.right)]
}
迭代
const preorderTraversal = (root: TreeNode | null): number[] => {
const ans: number[] = []
const stack: TreeNode[] = [root]
while (stack.length > 0) {
const node = stack.pop()
if (node == null) continue
ans.push(node.val)
stack.push(node.right)
stack.push(node.left)
}
return ans
}
中序遍历
递归
const inorderTraversal = (root: TreeNode | null): number[] => {
if (root == null) return []
return [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)]
}
迭代
const inorderTraversal = (root: TreeNode | null): number[] => {
const ans: number[] = []
const stack: TreeNode[] = []
let cur: TreeNode | null = root
while (stack.length > 0 || cur != null) {
if (cur != null) {
stack.push(cur)
cur = cur.left
} else {
cur = stack.pop()
ans.push(cur.val)
cur = cur.right
}
}
return ans
}
后序遍历
递归
const postorderTraversal = (root: TreeNode | null): number[] => {
if (root == null) return []
return [...postorderTraversal(root.left), ...postorderTraversal(root.right), root.val]
}
迭代
const postorderTraversal = (root: TreeNode | null): number[] => {
const ans: number[] = []
const stack: TreeNode[] = [root]
while (stack.length > 0) {
const node = stack.pop()
if (node == null) continue
ans.unshift(node.val)
stack.push(node.left)
stack.push(node.right)
}
return ans
}
层序遍历
递归
const levelOrder = (root: TreeNode | null): number[][] => {
const ans: number[][] = []
const dfs = (node: TreeNode | null, depth: number) => {
if (node == null) return null
ans[depth] = (ans[depth] || []).concat(node.val)
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
}
dfs(root, 0)
return ans
}
迭代
const levelOrder = (root: TreeNode | null): number[][] => {
if (root == null) return []
const ans: number[][] = []
const queue: TreeNode[] = [root]
while (queue.length > 0) {
const len = queue.length
const tmp: number[] = []
for (let i = 0; i < len; i++) {
const node = queue.shift()
tmp.push(node.val)
if (node.left != null) queue.push(node.left)
if (node.right != null) queue.push(node.right)
}
ans.push(tmp)
}
return ans
}
根据前、中、后遍历结果构建二叉树
前序&中序
const buildTree = (preorder: number[], inorder: number[]): TreeNode | null => {
if (preorder.length == 0) return null
const root_val = preorder[0]
const root_index = inorder.indexOf(root_val)
return new TreeNode(
root_val,
buildTree(preorder.slice(1, root_index + 1), inorder.slice(0, root_index)),
buildTree(preorder.slice(root_index + 1), inorder.slice(root_index + 1))
)
}
中序&后序
const buildTree = (inorder: number[], postorder: number[]): TreeNode | null => {
if (postorder.length == 0) return null
const root_val = postorder.at(-1)
const root_index = inorder.indexOf(root_val)
return new TreeNode(
root_val,
buildTree(inorder.slice(0, root_index), postorder.slice(0, root_index)),
buildTree(inorder.slice(root_index + 1), postorder.slice(root_index, -1)),
)
}
前序&后序
const buildTree = (preorder: number[], postorder: number[]): TreeNode | null => {
if(preorder.length == 0) return null
const [root_val, sub_root_val] = [preorder[0], preorder[1]]
const sub_root_index = postorder.indexOf(sub_root_val)
return new TreeNode(
root_val,
buildTree(preorder.slice(1, sub_root_index + 2), postorder.slice(0, sub_root_index + 1)),
buildTree(preorder.slice(sub_root_index + 2), postorder.slice(sub_root_index + 1))
)
}