中序遍历二叉树.md

中序遍历二叉树

思路

• 先序：是二叉树遍历中的一种，即先访问根结点，然后遍历左子树，后遍历右子树。遍历左、右子树时，先访问根结点，后遍历左子树，后遍历右子树，如果二叉树为空则返回。

• 中序：是二叉树遍历中的一种，即先遍历左子树，后访问根结点，然后遍历右子树。若二叉树为空则结束返回。

• 后序：是二叉树遍历中的一种，即先遍历左子树，后遍历右子树，然后访问根结点，遍历左、右子树时，仍先遍历左子树，后遍历右子树，最后遍历根结点。

var inorderTraversal = function(root) {
    var 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);
}

迭代版

var inorderTraversal=function(root){
        var  res=[];
        //栈  
        var s=[];
        var p = root;

        while (p || s.length>0) {
            //直至左节点为空，即没有左节点为止
            while (p) {
                s.push(p);
                p = p.left;
            }
            //出栈，存放根节点
            p = s.pop();
            res.push(p.val);
            p = p.right;
        }
        return res;
}