中序遍历的递归和非递归解法

递归解法：左中右

function inorderTraversal( root ) {
    // write code here
    const res = [];
    inorder(root,res);
    return res;
}
function inorder(root,res){
    if(!root) return;
    inorder(root.left,res);
    res.push(root.val);
    inorder(root.right,res);
}
module.exports = {
    inorderTraversal : inorderTraversal
};

非递归解法：栈和指针的思想

function inorderTraversal( root ) {
    // write code here
    let res = [];
    if(!root) return res;
    let p = root;
    let q = [];
    
    while(q.length || p ){
        while(p){
            q.push(p);
            p = p.left;
        }
        //console.log(q)
        let qHead = q.pop();
        res.push(qHead.val);
        p = qHead.right;
    }
    return res;
}