代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
递归遍历或利用栈实现非递归遍历。
非递归的思路如下：
先序遍历的顺序是：头、左、右，如果我们改变左右孩子的顺序，就能将顺序变成：头、右、左。
我们先不打印头节点，而是存放到另一个收集栈 s2 中，最后遍历结束，输出收集栈元素，即是后序遍历：左、右、头。
递归：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
res.append(root.val)
res = []
postorder(root)
return res
非递归：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
s1 = [root]
s2 = []
while s1:
node = s1.pop()
s2.append(node.val)
if node.left:
s1.append(node.left)
if node.right:
s1.append(node.right)
return s2[::-1]
递归：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private List<Integer> res;
public List<Integer> postorderTraversal(TreeNode root) {
res = new ArrayList<>();
postorder(root);
return res;
}
private void postorder(TreeNode root) {
if (root != null) {
postorder(root.left);
postorder(root.right);
res.add(root.val);
}
}
}
非递归：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
if (root == null) {
return Collections.emptyList();
}
Deque<TreeNode> s1 = new ArrayDeque<>();
List<Integer> s2 = new ArrayList<>();
s1.push(root);
while (!s1.isEmpty()) {
TreeNode node = s1.pop();
s2.add(node.val);
if (node.left != null) {
s1.push(node.left);
}
if (node.right != null) {
s1.push(node.right);
}
}
Collections.reverse(s2);
return s2;
}
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。