Traversal of binary tree

Traversal of binary tree

• Recursive Traversal of binary tree
• Iterative Traversal of binary tree
• Universal Iterative Traversal of binary tree
• Binary Tree Level Order Traversal

  Recursive Traversal of binary tree

  function TreeNode(val, left, right) {  this.val = val === undefined ? 0 : val;  this.left = left === undefined ? null : left;  this.right = right === undefined ? null : right;}const preorderTraversal = function (root, res) {  if (root === null) return;  res.push(root.val);  preorderTraversal(root.left, res);  preorderTraversal(root.right, res);};const inorderTraversal = function (root, res) {  if (root === null) return;  inorderTraversal(root.left, res);  res.push(root.val);  inorderTraversal(root.right, res);};const postorderTraversal = function (root, res) {  if (root === null) return;  postorderTraversal(root.left, res);  postorderTraversal(root.right, res);  res.push(root.val);};var traversal = function (root) {  let res = [];  postorderTraversal(root, res);  return res;};const tree1 = new TreeNode(1, null, new TreeNode(2, new TreeNode(3)));const tree2 = new TreeNode(1, new TreeNode(2), new TreeNode(3));const tree3 = new TreeNode(  1,  new TreeNode(    2,    new TreeNode(3, new TreeNode(4), new TreeNode(5)),    new TreeNode(6)  ));console.log(traversal(tree1));console.log(traversal(tree2));console.log(traversal(tree3));

  Iterative Traversal of binary tree

  function TreeNode(val, left, right) {  this.val = val === undefined ? 0 : val;  this.left = left === undefined ? null : left;  this.right = right === undefined ? null : right;}// mid - left - right(FILO)const preorderTraversal = function (root, res, stack) {  if (root === null) return;  stack.push(root);  while (stack.length) {    let node = stack.pop();    res.push(node.val);    if (node.right) {      stack.push(node.right);    }    if (node.left) {      stack.push(node.left);    }  }  return res;};const inorderTraversal = function (root, res, stack) {  if (root === null) return;  let node = root;  while (node != null || stack.length) {    if (node != null) {      stack.push(node);      node = node.left;    } else {      node = stack.pop();      res.push(node.val);      node = node.right;    }  }  return res;};const postorderTraversal = function (root, res, stack) {  if (root === null) return;  stack.push(root);  while (stack.length) {    let node = stack.pop();    res.push(node.val);    if (node.left) {      stack.push(node.left);    }    if (node.right) {      stack.push(node.right);    }  }  return res.reverse();};var traversal = function (root) {  let res = [];  let stack = [];  postorderTraversal(root, res, stack);  return res;};const tree1 = new TreeNode(1, null, new TreeNode(2, new TreeNode(3)));const tree2 = new TreeNode(1, new TreeNode(2), new TreeNode(3));const tree3 = new TreeNode(  1,  new TreeNode(    2,    new TreeNode(3, new TreeNode(4), new TreeNode(5)),    new TreeNode(6)  ));console.log(traversal(tree1));console.log(traversal(tree2));console.log(traversal(tree3));

  Universal Iterative Traversal of binary tree

  将访问的节点直接加入到栈中，但如果是处理的节点则后面放入一个空节点， 这样只有空节点弹出的时候，才将下一个节点放进结果集。

  （）

  // 前序遍历：中左右// 压栈顺序：右左中var preorderTraversal = function (root, res = []) {  const stack = [];  if (root) stack.push(root);  while (stack.length) {    const node = stack.pop();    if (!node) {      res.push(stack.pop().val);      continue;    }    if (node.right) stack.push(node.right); // 右    if (node.left) stack.push(node.left); // 左    stack.push(node); // 中    stack.push(null);  }  return res;};//  中序遍历：左中右//  压栈顺序：右中左var inorderTraversal = function (root, res = []) {  const stack = [];  if (root) stack.push(root);  while (stack.length) {    const node = stack.pop();    if (!node) {      res.push(stack.pop().val);      continue;    }    if (node.right) stack.push(node.right); // 右    stack.push(node); // 中    stack.push(null);    if (node.left) stack.push(node.left); // 左  }  return res;};// 后续遍历：左右中// 压栈顺序：中右左var postorderTraversal = function (root, res = []) {  const stack = [];  if (root) stack.push(root);  while (stack.length) {    const node = stack.pop();    if (!node) {      res.push(stack.pop().val);      continue;    }    stack.push(node); // 中    stack.push(null);    if (node.right) stack.push(node.right); // 右    if (node.left) stack.push(node.left); // 左  }  return res;};

  Binary Tree Level Order Traversal

  function TreeNode(val, left, right) {  this.val = val === undefined ? 0 : val;  this.left = left === undefined ? null : left;  this.right = right === undefined ? null : right;}const levelOrderTraversal = function (root, res, queue) {  if (root === null) return [];  queue.push(root);  while (queue.length !== 0) {    const length = queue.length; // the length of root array: 7    let level = []; // store each level array    for (let i = 0; i                                                 （）