二叉树的遍历

二叉树的遍历

• 先序遍历 - 根左右
• 中序遍历 - 左根右
• 后序遍历 - 左右根
• 层次遍历

递归 - 前中后续遍历

// 前序遍历
// 根左右
function preOrderTrans(root) {
  function preOrder(root, result) {
    if (root) {
      result.push(root);
      if (root.left) {
        preOrder(root.left, result);
      }
      if (root.right) {
        preOrder(root.right, result);
      }
    }
    return result;
  }
  return preOrder(root, []);
}

// 中序遍历
function inOrderTrans(root) {
  function inOrder(root, result) {
    if (root) {
      if (root.left) {
        inOrder(root.left, result);
      }
      result.push(root);
      if (root.right) {
        inOrder(root.right, result);
      }
    }
    return result;
  }
  return inOrder(root, []);
}

// 后序遍历

function postOrderTrans(root) {
  function postOrder(root, result) {
    if (root) {
      if (root.left) {
        postOrder(root.left, result);
      }
      if (root.right) {
        postOrder(root.right, result);
      }
      result.push(root);
    }
    return result;
  }
  return postOrder(root, []);
}

非递归 - 前中后序遍历

// 非递归
// 先序遍历
// 根左右
function preOrderTrans(root) {
  const result = [];
  const stack = [];
  if (root) {
    stack.push(root);
    while (stack.length) {
      const node = stack.pop();
      result.push(node.val);
      if (node.right) {
        stack.push(node.right);
      }
      if (node.left) {
        stack.push(node.left);
      }
    }
  }
  return result;
}

// 中序遍历
// 左根右

function inOrderTrans(root) {
  const result = [];
  let cur = root;
  const stack = [];
  while (stack.length || cur) {
    if (cur) {
      stack.push(cur);
      cur = cur.left;
    } else {
      // 访问节点
      cur = stack.pop();
      result.push(cur.value);
      cur = cur.right;
    }
  }
  return result;
}

// 后序遍历
// 左右根
// 根右左
// 根左右
function postOrderTrans(root) {
  const result = [];
  const stack = [];
  if (root) {
    stack.push(root);
    while (stack.length) {
      const node = stack.pop();
      result.push(node.val);
      if (node.left) {
        stack.push(node.left);
      }
      if (node.right) {
        stack.push(node.right);
      }
    }
  }
  return result.reverse();
}

二叉树的层次遍历

function levelOrderTrans(root) {
  const result = [];
  if (root) {
    const queue = [root];
    while (queue.length) {
      const cur = [];
      const len = queue.length;
      for (let i = 0; i < len; i++) {
        const node = queue.shift();
        cur.push(node.val);
        if (node.left) {
          queue.push(node.left);
        }
        if (node.right) {
          queue.push(node.right);
        }
      }
      result.push(cur);
    }
  }
  return result;
}