Cocolib

Appearance

On this page

前后中序的迭代写法 ​

前序遍历 ​

要访问的元素和要处理的元素顺序是一致的，都是中间节点。

js
var preorderTraversal = function(root) {
    let stack = []  //栈
    let ans = []    //结果
    stack.push(root)	//1、根节点入栈
    while(stack!=[]){
        p = stack.pop()
        if(p==null) return ans		//终止条件！！！很重要！！
            ans.push(p.val)			//2、中节点值存入数组
        if(p.right!=null)
            stack.push(p.right)		//3、右节点入栈
        if(p.left!=null)
            stack.push(p.left)		//4、左节点入栈
    }
    return ans
};

中序遍历 ​

中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。

js
var inorderTraversal = function(root) {
    let stack = []  //栈：用于存放未处理的节点
    let ans = []    //结果
    let cur = root  //指针：用于定位要处理的节点
    while(cur!=null||stack.length!=0){      //注意这里的终止条件
        if(cur!=null){  
            stack.push(cur)
            cur = cur.left  //做这种取左右节点的操作时一定记得先判空！！！
        }else{      // 指针来访问节点，访问到最底层
            cur = stack.pop()
            ans.push(cur.val)
            cur = cur.right
        }
    }
    return ans
};

后序遍历 ​

再来看后序遍历，先序遍历是中左右，后序遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了

js
var postorderTraversal = function(root) {
    const stack = []  //栈
    const ans = []    //结果
    stack.push(root)	//1、根节点入栈
    while(stack!=[]){
        p = stack.pop()
        if(p==null) break		//终止条件！！！很重要！！
            ans.push(p.val)			//2、中节点值存入数组
        if(p.left!=null)
            stack.push(p.left)		//3、左节点入栈
        if(p.right!=null)
            stack.push(p.right)		//4、右节点入栈
    }
    const reversed = ans.reverse()
    return reversed
};