给你一棵二叉树的根节点 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
(1)回溯
//思路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);
}
}
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/weixin_43004044/article/details/123769368
内容来源于网络,如有侵权,请联系作者删除!