AlgoPressAppearance
0145-二叉树的后续遍历
https://leetcode.cn/problems/binary-tree-postorder-traversal
给定一个二叉树，返回它的 后序遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
进阶:递归算法很简单，你可以通过迭代算法完成吗？
思路：递归dfs
参考代码
csharp
public class Solution {
List<int> list;
private void dfs(TreeNode root){
if(root == null){
return;
}
dfs(root.left);
dfs(root.right);
list.Add(root.val);
}
public IList<int> PostorderTraversal(TreeNode root) {
list = new List<int>();
dfs(root);
return list;
}
}
思路2： 迭代(栈)
参考代码
csharp
public class Solution{
public IList<int> PostorderTraversal(TreeNode root){
List<int> list = new List<int>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = root;
TreeNode prev ;
while(node != null || stack.Count > 0){
while(node != null){
stack.Push(node);
node = node.left;
}
node = stack.Pop();
//后续节点遍历不能直接加入
//需要判断没有后续节点了(node.right == null) 或者节点已经处理过了 (node.right == prev)
if(node.right == null || node.right == prev){
list.Add(node.val);
prev = node;
node = null; //结束循环
}
else{
stack.Push(node);
node = node.right;
}
}
return list;
}
}