二叉树的先中后序遍历

作者:Annan

更新于:几秒前

字数统计:169 字

阅读时长:1 分钟

阅读量:

先序遍历 根左右

递归

var preorderTraversal = function(root) {
  const res = []
  const dfs = (root) => {
    if(root === null) return
    res.push(root.val)
    dfs(root.left)
    dfs(root.right)
  }
  dfs(root)
  return res
};

栈

var preorderTraversal = function(root) {
  if (!root) return;
  const res = []
  const stack = [root];
  while (stack.length > 0) {
    const node = stack.pop();
    res.push(node.val)
    // 注意：因为栈是LIFO，所以先压入右子节点，再压入左子节点
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  return res
};

中序遍历 左根右

递归

var inorderTraversal = function(root) {
  const res = []
  const dfs = (root) => {
    if(root === null) return
    dfs(root.left)
    res.push(root.val)
    dfs(root.right)
  }
  dfs(root)
  return res
};

后序遍历 左右根

递归

var postorderTraversal = function(root) {
  const res = []
  const dfs = (root) => {
    if(root === null) return
    dfs(root.left)
    dfs(root.right)
    res.push(root.val)
  }
  dfs(root)
  return res
};

Contributors

Annan