来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
题目
给定一个二叉树,返回它的后序遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
思路
借鉴了力扣上一个很牛掰的解法:
- 后续遍历是左->右->中的顺序,那就可以自定向下,拿到中->右->左的值,倒叙后即是结果;
- 从root节点开始,如果不为空,入栈,并将val放在LinkedList的队头;
- 然后将root节点指向右子节点,继续第2步;
- 如果节点为空,则将上一个节点出栈,root指向其左子节点,继续第2步;
- 若root为空,且stack为空,入栈的节点已全部出栈,则该二叉树已经遍历完毕,返回result即可。
代码
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> result = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
if (root != null) {
stack.push(root);
result.addFirst(root.val);
root = root.right;
} else {
root = stack.pop();
root = root.left;
}
}
return result;
}
网友评论