SOURCE

// 前序便利  根左右
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(root) {

//     if (root) {
//         console.log(root.value);
//         preOrder(root.left);
//         preOrder(root.right);
//     }
// }

 var preOrder = function (root, array = []) {
      if (root) {
        preOrder(root.left, array);
        array.push(root.value);
        preOrder(root.right, array);
      }
      return array;
    };

function inOrder(root) {
    if (root) {
        inOrder(root.left);
        console.log(root.value);
        inOrder(root.right);
    }
}


function postOrder(root) {
    if (root) {
        postOrder(root.left);
        postOrder(root.right);
        console.log(root.value);
    }
}

// console.log(preOrder(tree))
// console.log(inOrder(tree))
// console.log(postOrder(tree))


// 非递归半
var preOrderNew = function(node) {
  const result = [];
  const stack = []

  stack.push(node)
  while(stack.length > 0) {
    const current = stack.pop();
    result.push(current.value);
    if(current.right) stack.push(current.right)
    if(current.left) stack.push(current.left)
  }

  return result;
}


var levelOrderTraversal = function(node) {
    const result = [];
    const que = []

  if (node) {
    que.push(node)
    while(que.length !== 0) {
        const current = que.shift()   // 先进先出
        result.push(current.value)
        if(current.left) que.push(current.left)
        if(current.right) que.push(current.right)
    }

    return result;
  }

}


// console.log(preOrderNew(tree))

    var inorderTraversal = function (root) {
      const result = [];
      const stack = [];
      let current = root;
      while (current || stack.length > 0) {
        // 最左边一条线，从根-叶子节点依次入栈
        // current代表上一个节点的右侧，无右侧不进
        while (current) {
          stack.push(current);
          current = current.left;
        }

        // 弹出时记录值
        current = stack.pop();
        result.push(current.value);

        current = current.right;
      }
      return result;
    };

    console.log(inorderTraversal(tree));

var inorderTraversal = function(root) {
    const result = [];
    if(!root) return [];

    const stack = [root];
    while(stack.length > 0){
        // 1、左子节点迭代入栈
        while(root.left){
            root = root.left;
            stack.push(root);
        }

        // 2、出栈，记录值
        let cur = stack.pop();
        result.push(cur.value);

        // 3、cur的右子节点存在时，（走1、把该右子节点，及所有的左子节点迭代入栈）
        if(cur.right){
            root = cur.right;
            stack.push(root);
        }
    }
    return result;
};

const dsa = {
  value: 1,
  left: {
    value: 2,
    left: {
      value: 4,
    },
    right: {
      value: 5,
      left: {
        value: 6,
      },
      right: {
        value: 7
      }
    }
  },
  right: {
    value: 3
  }
}
console.log('inorderTraversal', inorderTraversal(dsa));


function inOrderTest(root) {
    const result = [];
    if (!root) return []

    const stack = [root];

    while(stack.length > 0) {
        // 迭代左子节点
        while(root.left) {
            root = root.left;
            stack.push(root);
        }

        // 取
        let cur = stack.pop();
        result.push(cur.value);

        // 如果有右子节点
        if (cur.right) {
            root = cur.right
            stack.push(root);
        }
    }

    return result;
}

console.log(inOrderTest(dsa));

 var postorderTraversal = function (root) {
      const result = [];
      const stack = [];
      let last = null; // 标记上一个访问的节点
      let current = root;
      while (current || stack.length > 0) {
        while (current) {
          stack.push(current);
          current = current.left;
        }
        current = stack[stack.length - 1];
        if (!current.right || current.right == last) {
          current = stack.pop();
          result.push(current.value);
          last = current;
          current = null; // 继续弹栈
        } else {
          current = current.right;
        }
      }
      return result;
    }


    var postorderTraversal22 = function(root) {
    let stack = [], res = []
    root && stack.push(root)
    while(stack.length > 0) {
        let cur = stack.pop()
        res.push(cur.value)
        cur.left && stack.push(cur.left)
        cur.right && stack.push(cur.right)
    }
    return res.reverse()
};

    console.log(99, postorderTraversal(dsa), postorderTraversal22(dsa));