二叉树

在 JavaScript 中，你可以使用递归或迭代的方式来实现二叉树的前序、中序和后序遍历。下面是使用递归方式实现的示例代码：

递归遍历

// 定义二叉树节点
class TreeNode {
  constructor(val, left, right) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// 前序遍历
function preorderTraversal(root) {
  const result = [];
  
  function traverse(node) {
    if (node === null) return;
    
    result.push(node.val);
    traverse(node.left);
    traverse(node.right);
  }
  
  traverse(root);
  return result;
}

// 中序遍历
function inorderTraversal(root) {
  const result = [];
  
  function traverse(node) {
    if (node === null) return;
    
    traverse(node.left);
    result.push(node.val);
    traverse(node.right);
  }
  
  traverse(root);
  return result;
}

// 后序遍历
function postorderTraversal(root) {
  const result = [];
  
  function traverse(node) {
    if (node === null) return;
    
    traverse(node.left);
    traverse(node.right);
    result.push(node.val);
  }
  
  traverse(root);
  return result;
}

// 创建二叉树
const tree = new TreeNode(1);
tree.left = new TreeNode(2);
tree.right = new TreeNode(3);
tree.left.left = new TreeNode(4);
tree.left.right = new TreeNode(5);

// 测试
console.log(preorderTraversal(tree));   // 前序遍历结果：[1, 2, 4, 5, 3]
console.log(inorderTraversal(tree));    // 中序遍历结果：[4, 2, 5, 1, 3]
console.log(postorderTraversal(tree));  // 后序遍历结果：[4, 5, 2, 3, 1]

迭代遍历

function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
}
// 前序遍历
var preorderTraversal = function(root) {
    if (root === null) {
        return [];
    }
    const result = [];
    const stack = [];
    stack.push(root);
    while(stack.length > 0) {
        const node = stack.pop();
        result.push(node.val);
        if (node.right !== null) {
            stack.push(node.right);
        }
        if (node.left !== null) {
            stack.push(node.left);
        }
    }
    return result;
};
// 中序遍历
var inorderTraversal = function (root) {
    const result = [];
    const stack = [];
    let current = root;
    while (current !== null || stack.length > 0) {
        while (current !== null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        result.push(current.val);
        current = current.right;
    }
    return result;
};
// 后续遍历
var postorderTraversal = function (root) {
    if (root === null) {
        return [];
    }
    const result = [];
    const stack = [];
    let current = root;
    let lastVisited = null;

    while (current !== null || stack.length > 0) {
        if (current !== null) {
            stack.push(current);
            current = current.left;
        } else {
            const peekNode = stack[stack.length - 1];
            if (peekNode.right !== null && lastVisited !== peekNode.right) {
                current = peekNode.right;

            } else {
                result.push(peekNode.val);
                lastVisited = stack.pop();
            }
        }
    }
    return result;
};

// 创建二叉树
const root = new TreeNode(1);
const node2 = new TreeNode(2);
const node3 = new TreeNode(3);

root.right = node2;
node2.left = node3;
// 层序遍历
const result1 = preorderTraversal(root);
const result2 = inorderTraversal(root);
const result3 = postorderTraversal(root);
// 打印结果
console.log(result1);
console.log(result2);
console.log(result3);

二叉树深度

// [队列 ]使用一个队列 queue 来进行广度优先搜索。首先将根节点放入队列中，然后不断迭代直到队列为空。在每一轮迭代中，我们先记录当前队列的大小 size，然后依次取出队列中的节点，并将它们的左右子节点（如果存在）加入队列。这样，每一轮迭代都表示一层的节点被访问过。最后，返回迭代的次数，即为二叉树的最大深度。
var calculateDepth = function (root) {
    if (root === null) {
        return 0;
    }
    let depth = 0;
    const queue = [root];

    while (queue.length > 0) {
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
        }
        depth++;
    }
    return depth;
};
// [递归]如果当前节点为空，表示到达叶子节点的子节点，返回深度0。否则，递归计算左子树和右子树的最大深度，然后取两者中的较大值，并加上当前节点的深度1，作为当前子树的最大深度。
var calculateDepth = function (root) {
    if (root === null) {
        return 0;
    }
    const leftDepth = calculateDepth(root.left);
    const rightDepth = calculateDepth(root.right);
    return Math.max(leftDepth, rightDepth) + 1;
};

图遍历算法

BFS（广度优先搜索）和DFS（深度优先搜索）是两种常用的图遍历算法，它们也可以用于遍历二叉树。下面分别介绍它们在二叉树中的实现方式：

BFS（广度优先搜索）

BFS使用队列来实现，按照层级顺序逐层遍历二叉树。具体步骤如下：

1. 创建一个队列，并将根节点入队。
2. 当队列不为空时，执行以下步骤：
   • 出队一个节点，并访问该节点。
   • 将该节点的左子节点和右子节点（如果存在）依次入队。
   • 重复步骤2直到队列为空。

DFS（深度优先搜索）

DFS有两种常见的实现方式：递归和迭代。

递归实现DFS：
递归实现DFS是最直观的方式，它可以通过递归函数来实现。具体步骤如下：

1. 定义一个递归函数，传入当前节点作为参数。
2. 如果当前节点为空，返回。
3. 访问当前节点。
4. 递归调用函数遍历当前节点的左子节点。
5. 递归调用函数遍历当前节点的右子节点。

迭代实现DFS：
迭代实现DFS可以使用栈来辅助实现。具体步骤如下：

1. 创建一个栈，并将根节点入栈。
2. 当栈不为空时，执行以下步骤：
   • 出栈一个节点，并访问该节点。
   • 将该节点的右子节点（如果存在）入栈。
   • 将该节点的左子节点（如果存在）入栈。
     重复步骤2直到栈为空。
     无论是BFS还是DFS，它们都可以用于遍历二叉树，并根据需要执行相应的操作。选择使用哪种方式取决于具体的需求和问题。

赏

谢谢你请我吃糖果