二叉树的遍历

Tags

algorithm

Created

Nov 30, 2015 5:32 PM

例子：寻找两个 node 的公共父节点

// node 不含父节点引用

解：使用深度遍历二叉树，递归找到节点，返回为 List（节点路径），比较两个 List，找到最后一个相同的节点

先序遍历：若二叉树非空，访问根结点，遍历左子树，遍历右子树。

A-B-C-D-E-F-G

中序遍历：若二叉树非空，遍历左子树；访问根结点；遍历右子树。

C-B-D-A-E-G-F

// 如果用递归算法，由于改变了递归顺序，所以最终改变了遍历到的节点

后序遍历：若二叉树非空，遍历左子树；遍历右子树；访问根结点。

C-D-B-G-F-E-A

广度遍历(BFS)

A-B-E-C-D-F-G

function traversal(rt) {
  const nodes = [];
  const queue = [rt]; // 队列
  while (queue.length) {
    const node = queue.shift(); // 先进先出
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
    nodes.push(node);
  }
  return nodes;
}

深度遍历(DFS)

求合法括号对组合，如 ['()()', '(())']

将所有组合生成二叉树
深度遍历，左括号数比右括号数多即为合法

function traversal(rt) {
  const result = [];
  const pathMap = new Map([[rt, [rt]]]);
  const stack = [rt];
  while (stack.length) {
    const node = stack.pop();



    const path = pathMap.get(node);



    if (node.right) {
      stack.push(node.right);
      pathMap.set(node.right, [...path, node.right]);
    }



    // 后压先出
    if (node.left) {
      stack.push(node.left);
      pathMap.set(node.left, [...path, node.left]);
    }



    if (!node.left && !node.right) {
      result.push(path);
    }
  }
  return result;
}