day13-使用js实现树的先中后序遍历

不使用递归

class TreeNode {
  constructor(val,left=null,right=null){
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

const root= new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);

// 前序
function inorderTraversal(root){
  if(!root) return [];
  const stack = [root];
  const res = [];
  while(stack.length){
    const node = stack.pop();
    res.push(node.val)
    if(node.right){
      stack.push(node.right)
    }
    if(node.left){
      stack.push(node.left)
    }
  }
  return res;
}

// 中序
function middeTraversal(root){
  if(!root) return [];
  let cur = root;
  const stack = [];
  const res = [];
  while(stack.length || cur){
    // 找左子树
    while(cur){
      stack.push(cur);
      cur = cur.left;
    }
    cur = stack.pop();
    res.push(cur.val);
    cur = cur.right;
  }
  return res;
}

// 后序遍历
function postorderTraversal(root){
  if (!root) return [];
  const stack = [];
  const res = [];
  let lastVisibleNode = null;
  let cur = root;
  while (cur || stack.length) {
    // 找到最左侧子节点
    if (cur) {
      stack.push(cur);
      cur = cur.left;
    } else {
      // 左侧已找到最后 取出最后一个入栈的节点 
      const peekNode = stack[stack.length - 1];
      // 如果有右节点 
      if (peekNode.right && peekNode.right !== lastVisibleNode) {
        cur = peekNode.right;
      } else {
        // 当前节点就是要遍历的最新节点
        lastVisibleNode = stack.pop();
        res.push(lastVisibleNode.val);
      }
    }
  }
  return res;
}