深度&广度优先遍历

深度优先

深度优先

深度优先遍历就是当我们搜索一个树的分支时，遇到一个节点，我们会优先遍历它的子节点直到最后根节点为止，最后再遍历兄弟节点，从兄弟子节点寻找它的子节点，直到搜索到最后结果

const deepDFS = (root, nodeList = []) => {
  if(root === null) return
  nodeList.push(root.val)
  if(root.left) deepDFS(root.left, nodeList)
  if(root.right) deepDFS(root.right, nodeList)
  return nodeList
}

广度优先

广度优先

从根节点开始，当访问子节点时，先遍历找到兄弟节点，再寻找对应自己的子节点

const deepBFS = (root) => {
  const nodeList = []
  if(root.val) nodeList.push(root.val)
  const queue = [root]
  while(queue.length > 0){
    const node = queue.shift();
    node.left && nodeList.push(node.left.val)
    node.right && nodeList.push(node.right.val)
    if(node.left) queue.push(node.left)
    if(node.right) queue.push(node.right)
  }
}

catGPT实现：

function deepBFS(root) {
    if (!root) {
        return [];
    }
    let result = [];
    let queue = [root];

    while (queue.length > 0) {
        let node = queue.shift();
        result.push(node.val);
        if (node.left) {
            queue.push(node.left);
        }
        if (node.right) {
            queue.push(node.right);
        }
    }
    return result;
}

测试用例：

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

// 构建一个二叉树
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);

// 广度优先遍历二叉树
console.log(breadthFirstSearch(root)); // 输出：[1, 2, 3, 4, 5, 6, 7]