青岛网站建设效果,公司网络营销的方案,重庆企业网站推广价格,国家网站备案145. 二叉树的后序遍历
给你一棵二叉树的根节点 root #xff0c;返回其节点值的 后序遍历 。
示例 1#xff1a; 输入#xff1a;root [1,null,2,3]
输出#xff1a;[3,2,1]示例 2#xff1a;
输入#xff1a;root []
输出#xff1a;[]示例 3#xff1a;
输入返回其节点值的 后序遍历 。
示例 1 输入root [1,null,2,3]
输出[3,2,1]示例 2
输入root []
输出[]示例 3
输入root [1]
输出[1]提示
树中节点的数目在范围 [0, 100] 内-100 Node.val 100 进阶递归算法很简单你可以通过迭代算法完成吗
解法思路 1、递归 2、迭代 法一
/*** 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 ListInteger postorderTraversal(TreeNode root) {// Recursion// Time: O(n)// Space: O(n)ListInteger res new ArrayList();postorder(root, res);return res;}private void postorder(TreeNode root, ListInteger res) {if (root null) return;postorder(root.left, res);postorder(root.right, res);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 ListInteger postorderTraversal(TreeNode root) {// Iterator// Time: O(n)// Space: O(n)ListInteger res new ArrayList();if (root null) return res;DequeTreeNode stack new ArrayDeque();TreeNode prev null;while (root ! null || !stack.isEmpty()) {while (root ! null) {stack.addLast(root);root root.left;}root stack.removeLast();if (root.right null || root.right prev) {res.add(root.val);prev root;root null;} else {stack.addLast(root);root root.right;}}return res;}
}
