二叉树的递归和非递归js实现

二叉树的基本结构

const node = {
    val: 'F',
    left: {
        val: 'B',
        left: { val: 'A' },
        right: { val: 'D', left: { val: 'C' }, right: { val: 'E' } }
    },
    right: { val: 'G', right: { val: 'I', left: { val: 'H' } } }
};

前序遍历

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。

递归实现

const PreTravelNode = (node, path = []) => {
    if (!node) return [];

    path = [...path, node.val];
    if (node.left) {
        path = [...path, ...PreTravelNode(node.left)];
    }
    if (node.right) {
        path = [...path, ...PreTravelNode(node.right)];
    }
    return path;
};

非递归实现

// 前序非递归
const PreTravelNode = root => {
  if (!root) {
    return [];
  }
  let p = root;
  let result = []; // 结果列表
  let stack = []; // 节点
  while (stack.length != 0 || p != null) {
     if (p != null) {
      stack.push(p);
      result.push(p.val);
      p = p.left;
    } else {
      p = stack.pop();
      p = p.right;
    }
  return result;
};

中序遍历

中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。

递归实现

const MidTravelNode = (node, path = []) => {
    if (!node) return [];
    if (node.left) {
        path = [...path, ...MidTravelNode(node.left)];
    }
    path = [...path, node.val];

    if (node.right) {
        path = [...path, ...MidTravelNode(node.right)];
    }
    return path;
};

后序遍历

后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。

递归实现

const AfterTravelNode = (node, path = []) => {
    if (!node) return [];
    if (node.left) {
        path = [...path, ...AfterTravelNode(node.left)];
    }

    if (node.right) {
        path = [...path, ...AfterTravelNode(node.right)];
    }
    path = [...path, node.val];
    return path;
};