力扣 145. 二叉树的后序遍历
递归解法我不再赘述。我讲一下迭代解法。迭代解法处理后序遍历的关键是处理根节点在第二次访问的时候它的值才会被加入到List。
所以需要用到一个prev变量保存当前节点的右孩子节点。
从根节点一直向左遍历的同时把遍历到的节点入栈,当遍历到最左侧节点的左孩子是null,结束内层的循环,然后出栈,这是出栈的是最左侧节点,如果最左侧节点的右孩子是null或者是第二次经过这个节点,就把这个节点的数据域加入到List。否则就把当前节点指向当前节点的右孩子。
public List<Integer> postorderTraverse(TreeNode root){
List<Integer> lists=new ArrayList<>();
Stack<TreeNode> stack=new Stack<>();
TreeNode prev=null;
while(root!=null || !stack.isEmpty()){
while(root!=null){
stack.push(root);
root=root.left;
}
root=stack.pop();
if(root.right==null||root.right==prev){
lists.add(root.val);
prev=root;
root=null;
} else {
stack.push(root);
root=root.right;
}
}
return lists;
}