1.以中序遍历为例

    1. var inorderTraversal = function(root) {
    2.   if (!root) {
    3.     return []
    4.   }
    5.   const res = [];
    6.   const stack = [{mark: false,node: root}];
    7.   while(stack.length > 0) {
    8.     const {mark, node} = stack.pop();
    9.     if (node === null) {
    10.       continue;
    11.     }
    12.     if (!mark) {
    13.       // stack的顺序和遍历顺序相反 中序遍历 左、根、右 =====》 右、根、左
    14.       stack.push({mark: false, node: node.right});
    15.       stack.push({mark: true, node: node});
    16.       stack.push({mark: false, node: node.left});
    17.     } else {
    18.       res.push(node.val);
    19.     }
    20.   }
    21.   return res;
    22. };