// 中序遍歷，左中右
var TreeNode = {
    val: 1,
    left: {
        val: 2,
        left: {
          val: 4,
        },
        right: {
            val: 5
        }
    },
    right: {
        val: 3,
        left: {
            val: 6,
        },
        right: {
            val: 7
        }
    }
};


var inOrderRecur = function (root) {
    var list = [];
    var inOrder = function(root){
        if (root === undefined) {
            return root;
        }
        inOrder(root.left);
        list.push(root.val);
        inOrder(root.right);
    }
    inOrder(root)
    return list;
}

var inOrderUnRecur = function(root){
    var stack = [];
    var list = [];
    var head = root;
    while(stack.length !== 0 || head !== undefined){
        while(head !== undefined){
            stack.push(head);
            head = head.left;
        }

        if(stack.length !== 0){
            head = stack.pop();
            list.push(head.val);
            head = head.right;
        }
    }
    return list;
};

// var listRecur = inOrderRecur(TreeNode);
// console.log('遞歸中序遍歷',listRecur);

var listUnRecur = inOrderUnRecur(TreeNode);
console.log('非遞歸中序遍歷',listUnRecur);

// [4, 2, 5, 1, 6, 3, 7]