LeetCode-二叉树非递归后续遍历

解题记录
141 words , 1 mins.

周末突然降温，哪儿也去不了，不如在家刷题。

题目描述

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree{1,#,2,3},

1
2
3
4
5
1
 \
  2
 /
3

return[3,2,1].

Note: Recursive solution is trivial, could you do it iteratively？

使用非递归方法后序遍历二叉树。

解题思路

二叉树后序遍历就是对每个节点按照左、右、中的顺序进行遍历。

详细的解析参见：二叉树遍历(先序、中序、后序) ，讲得非常详细易懂。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package com.postorder.raversal;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @author zhulongkun20@163.com
 * @since 2018/11/17 下午1:49
 */
public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();
        TreeNode pointer = root;
        TreeNode lastVisit = root;
        while (!stack.isEmpty() || pointer != null) {
            while (pointer != null) {
                stack.push(pointer);
                pointer = pointer.left;
            }
            pointer = stack.peek();
            if (pointer.right == null || pointer.right == lastVisit) {
                list.add(pointer.val);
                lastVisit = pointer;
                stack.pop();
                pointer = null;
            } else {
                pointer = pointer.right;
            }
        }
        return list;
    }
}

是时候好好重修一下数据结构了。