前端面试题目收集（持续更新）

导读

二叉树是数据结构算法的重要知识点，今天我们用js来实现下二叉树的深度优先遍历

首先，生成一个二叉树

/*
二叉树
*/
var tree = {
  value: 1,
  left: {
    value: 2,
    left: {
      value: 4
    }
  },
  right: {
    value: 3,
    left: {
      value: 5,
      left: {
        value: 7
      },
      right: {
        value: 8
      }
    },
    right: {
      value: 6
    }
  }
}

前序遍历

• 递归

function preOrder(node) {
  if(node != null) {
    console.log(node.value)
    preOrder(node.left)
    preOrder(node.right)
  } 
}

• 非递归

function preOrder(root) {
  let stack = [];
  let pNode = root;
  while (pNode != null || !stack.length == 0) {
   if (pNode != null) {
    console.log(pNode.value+"  ");
    stack.push(pNode);
    pNode = pNode.left;
   } else { //pNode == null && !stack.isEmpty()
    node = stack.pop();
    pNode = node.right;
   }
  }
 }
preOrder(tree)

中序遍历

• 递归

function preOrder(node) {
  if(node != null) {
    preOrder(node.left)
    console.log(node.value)
    preOrder(node.right)
  } 
}

• 非递归

function midOrder(root) {
  let stack = [];
  let pNode = root;
  while (pNode != null || !stack.length == 0) {
   if (pNode != null) {
    stack.push(pNode);
    pNode = pNode.left;
   } else { //pNode == null && !stack.isEmpty()
    node = stack.pop();
        console.log(pNode.value+"  ");
    pNode = node.right;
   }
  }
 }
midOrder(tree)

后序遍历

• 递归

function preOrder(node) {
  if(node != null) {
    preOrder(node.left)
    preOrder(node.right)
    console.log(node.value)
  } 
}

• 非递归

var lastOrder = (root) => {
    let result = []
    let stack = []
    let node = root
    while(node != null || stack.length != 0){
        if(node != null) {
            result.unshift(node.value)
            stack.push(node)
            node = node.right
        }else{
            node = stack.pop()
            //console.log(node.value)
            node = node.left
        }
    }
    return result

}
lastOrder(tree)

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1249118795@qq.com