树

树的遍历

TIP

层序遍历属于广度优先遍历，前序遍历、中序遍历和后序遍历属于深度优先遍历

二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等。

广度优先遍历

/* 层序遍历 */
function levelOrder(root) {
    // 初始化队列，加入根节点
    const queue = [root];
    // 初始化一个列表，用于保存遍历序列
    const list = [];
    while (queue.length) {
        let node = queue.shift(); // 队列出队
        list.push(node.val); // 保存节点值
        if (node.left) queue.push(node.left); // 左子节点入队
        if (node.right) queue.push(node.right); // 右子节点入队
    }
    return list;
}

深度优先遍历

递归实现

/* 前序遍历 */
function preOrder(root) {
    if (root === null) return;
    // 访问优先级：根节点 -> 左子树 -> 右子树
    list.push(root.val);
    preOrder(root.left);
    preOrder(root.right);
}

/* 中序遍历 */
function inOrder(root) {
    if (root === null) return;
    // 访问优先级：左子树 -> 根节点 -> 右子树
    inOrder(root.left);
    list.push(root.val);
    inOrder(root.right);
}

/* 后序遍历 */
function postOrder(root) {
    if (root === null) return;
    // 访问优先级：左子树 -> 右子树 -> 根节点
    postOrder(root.left);
    postOrder(root.right);
    list.push(root.val);
}

栈实现

/* 前序遍历 */
const preOrderV2 = (root: TreeNode) => {
  const stack = [root];
  const list: string[] = [];
  while (stack.length) {
    const treeNode = stack.pop()!;
    list.push(treeNode.value);
    if (treeNode.right) {
      stack.push(treeNode.right);
    }
    if (treeNode.left) {
      stack.push(treeNode.left);
    }
  }
};
/* 中序遍历 */
const inOrderV2 = (root: TreeNode) => {
  const stack: TreeNode[] = [];
  const list: string[] = [];
  let current:TreeNode | undefined  = root;

  while (current || stack.length) {
    // 遍历到最左节点并压栈
    while (current) {
      stack.push(current);
      current = current.left;
    }
    // 弹出并访问节点
    current = stack.pop()!;
    list.push(current.value);
    // 处理右子树
    current = current.right;
  }
  return list;
};

/* 后序遍历 */
const postOrderV2 = (root) => {
    if (!root)
        return [];
    const stack1 = [root];
    const stack2 = [];
    while (stack1.length) {
        const node = stack1.pop();
        stack2.push(node); // 反转顺序的关键步骤
        // 注意左右子节点压栈顺序与常规相反
        if (node.left)
            stack1.push(node.left);
        if (node.right)
            stack1.push(node.right);
    }
    // 从 stack2 弹出即得到后序结果
    return stack2.reverse().map(node => node.value);
};

非二叉树的树结构

栈实现

type Tree={
    value:string
    children?:Tree[]
}
const traversal=(root:Tree)=>{
    const stack=[root]
    const list:string[]=[]
    while(stack.length){
        const tree=stack.pop()!
        list.push(tree.value)
        if(tree.children){
            for(let i=tree.children.length-1;i>=0;i--){
                stack.push(tree.children[i])
            }
        }
    }
}

递归实现

type Tree={
    value:string
    children?:Tree[]
}
const list:string[]=[]
const traversal=(root:Tree[])=>{
    root.forEach(child=>{
        list.push(child.value)
        if(child.children){
            traversal(child.children)
        }
    })
    return list
}

性能对比: 优先选择栈实现

大规模树结构	栈操作可控，内存稳定	递归深度过大时可能栈溢出