Tree structure and test cases

function TreeNode(val, left, right) {
  this.val = (val===undefined ? 0 : val);
  this.left = (left===undefined ? null : left);
  this.right = (right===undefined ? null : right);
}

// preorder: [1, 2, 4, 5, 7, 3, 6, 8, 9]
// inorder: [4, 2, 7, 5, 1, 3, 8, 6, 9]
// postorder: [4, 7, 5, 2, 8, 9, 6, 3, 1]
const testCase = new TreeNode(
  1.new TreeNode(2.new TreeNode(4), new TreeNode(5.new TreeNode(7))),
  new TreeNode(3.undefined.new TreeNode(6.new TreeNode(8), new TreeNode(9))))// or [1, 2, 3, 4, 5, null, 6, 7, null, 8, 9]
Copy the code
graph TB

1---2
1---3
2---4
2---5
5--left---7
3--right---6
6---8
6---9

recursive

// 1
function traversal1(root) {
  return root ? (
    // preorder
    [root.val, ...traversal(root.left), ...traversal(root.right)]
    // inorder
    // [...traversal(root.left), root.val, ...traversal(root.right)]
    // postorder
    // [...traversal(root.left), ...traversal(root.right), root.val]
  ) : [];
}

/ / 2.
function traversal2(root) {
  const result = [];
  
  function findNode(node) {
    if(! node)return;
  
    // preorder
    result.push(node.val);
    findNode(node.left);
    // inorder
    // result.push(node.val);
    findNode(node.right);
    // postorder
    // result.push(node.val);
  }
  
  findNode(root);
  return result;
}
Copy the code

The iteration

Preorder/middle order

// preorder and inorder
function traversal(root) {
  const result = [];
  const stack = [];
  
  while (stack.length || root) {
    while (root) {
      // preorder
      result.push(root.val);
      stack.push(root);
      root = root.left;
    }
    
    root = stack.pop();
    // inorder
    // result.push(root.val);
    root = root.right;
  }
  
  return result;
}
Copy the code

After the order

// 1. Reverse traversal from right to left, reverse traversal from forward, so also can be used for middle traversal
function postorderTraversal1(root) {
  const result = [];
  const stack = [];
  
  while (stack.length || root) {
    while (root) {
      // postorder
      result.unshift(root.val);
      stack.push(root);
      root = root.right;
    }
    
    root = stack.pop();
    // inorder
    // result.unshift(root.val);
    root = root.left;
  }
  
  return result;
}

// 2. Access the right child node mark (color mark)
// a. Push all the left children into the stack
// b. The top node has no right child or its right child is marked, store the result array, press the node and mark its right child
// c. The top node has a right child and the right child is unmarked. Repeat the ABC process
function postorderTraversal2(root) {
  const result = [];
  const stack = [];
  let visited;
  
  while (stack.length || root) {
    while (root) {
      stack.push(root);
      root = root.left;
    }
    
    root = stack[stack.length - 1];
    if(! root.right || (root.right === visited)) { root = stack.pop(); result.push(root.val); visited = root; root =null;
    } else{ root = root.right; }}return result;
}

// 3. Null notation (special color notation)
// The root node is pushed, the right node (if any), and the left node (if any), followed by null when the root node is pushed. The final order of storing nodes in the stack is root, NULL, right, left (child root), NULL... , the left child root node appends all nulls after it, so when the top left child is pushed out of the stack, the same loop is done to the right child of its sibling, resulting in an array of answers
function postorderTraversal3(root) {
  const result = [];
  const stack = [root];
  
  while (stack.length) {
    root = stack.pop();
    
    if (root) {
      stack.push(root, null);
      if (root.right) stack.push(root.right);
      if (root.left) stack.push(root.left);
    } else{ root = stack.pop(); result.push(root.val); }}return result;
}
Copy the code

Morris

Preorder/middle order

// preorder/inorder
function traversal(root) {
  const result = [];
  let predecessor;
  
  while (root) {
    if (root.left) {
    // The root node left child
      predecessor = root.left;
            
      // The left child of the root node finds the rightmost child
      while(predecessor.right && (predecessor.right ! == root)) { predecessor = predecessor.right; }if(! predecessor.right) {// The rightmost child adds the right node to be equal to the root node, so that the root pointer can return to the next node correctly after iterating back to this node
        predecessor.right = root;
        // preorder, push the root node into the result array before moving the pointer
        result.push(root.val);
        // The root pointer points to its left child and enters the loop
        root = root.left;
      } else {
        Right === root. At this point, it indicates that all the left children of the current root node have been fully traversed
        // inorder, after the left and root nodes are all traversed, add the right node (the root node of the next loop) to the result array
        // result.push(root.val);
        // Clear the changes to the original structure
        predecessor.right = null;
        // Start traversing the right child and enter the looproot = root.right; }}else {
      // The root node has no left child
      // preorder: The left child enters the result array
      // inorder: The left child enters the result array first, and the return loop enters the result array as the root node
      result.push(root.val);
      // Start right child, enter the looproot = root.right; }}return result;
};
Copy the code

After the order

function traversel(root) {
  const result = [];
  let predecessor;
  
  while (root) {
    if (root.right) {
      predecessor = root.right;
      
      while(predecessor.left && (predecessor.left ! == root)) { predecessor = predecessor.left; }if(! predecessor.left) { predecessor.left = root;// Postorder, the root node enters the result array first. The root should be entered in the order of right and left, so that the left and right roots can be reordered when reversing the array
        result.unshift(root.val);
        root = root.right;
      } else {
        // inorder, when the right child is completely traversed, insert the left child (i.e. the root node of the next loop)
        // result.unshift(root.val);
        predecessor.left = null; root = root.left; }}else {
      // Postorder enters the result array for the right child or for the root node with no right child
      // inorder, the root node of the right child or no right child enters the result array firstresult.unshift(root.val); root = root.left; }}return result;
}
Copy the code