LeetCode_二叉树_简单_145.二叉树的后序遍历
2023-09-27 14:25:46 时间
1.题目
给你一棵二叉树的根节点 root ,返回其节点值的后序遍历。
示例 1:
输入:root = [1,null,2,3]
输出:[3,2,1]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
提示:
树中节点的数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-postorder-traversal
2.思路
(1)回溯
3.代码实现(Java)
//思路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 {
//res保存后序遍历的结果
LinkedList<Integer> res = new LinkedList<>();
public List<Integer> postorderTraversal(TreeNode root) {
traverse(root);
return res;
}
public void traverse(TreeNode root) {
if (root == null) {
return;
}
//遍历当前根节点的左子树
traverse(root.left);
//遍历当前根节点的右子树
traverse(root.right);
//将当前根节点的值加入到res中
res.add(root.val);
}
}
相关文章
- Leetcode: Permutations
- 【Leetcode】110. 平衡二叉树(简单)
- 【Leetcode】107. 二叉树的层序遍历 II(中等)
- 【Leetcode】105. 从前序与中序遍历序列构造二叉树(中等)
- [leetcode]104. 二叉树的最大深度
- LeetCode搜索二叉树的练习
- 113、【树与二叉树】leetcode ——538. 把二叉搜索树转换为累加树:递增数组视角右中左遍历(C++版本)
- 108、【树与二叉树】leetcode ——235. 二叉搜索树的最近公共祖先:普通树解法+BST性质解法(C++版本)
- 90、【树与二叉树】leetcode ——104. 二叉树的最大深度:层次遍历+DFS+子问题分解(C++版本)
- 88、【树与二叉树】leetcode ——226. 翻转二叉树:先中后序的递归与DFS非递归遍历+BFS层次遍历(C++版本)
- 【LeetCode】105. Construct Binary Tree from Preorder and Inorder Traversal
- [LeetCode] 993. Cousins in Binary Tree 二叉树的表兄弟节点
- [LeetCode] 971. Flip Binary Tree To Match Preorder Traversal 翻转二叉树以匹配先序遍历
- [LeetCode] 987. Vertical Order Traversal of a Binary Tree 竖直遍历二叉树
- [LeetCode] Invert Binary Tree 翻转二叉树
- [LeetCode] 94. Binary Tree Inorder Traversal 二叉树的中序遍历
- [LeetCode] 144. Binary Tree Preorder Traversal 二叉树的先序遍历
- [LeetCode] 113. Path Sum II 二叉树路径之和之二
- LeetCode对称二叉树
- LeetCode二叉树中序遍历
- leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal 从中序与后序遍历序列构造二叉树(中等)
- leetcode算法257.二叉树的所有路径
- leetcode算法145.二叉树的后序遍历
- leetcode算法144.二叉树的前序遍历