石河子市住房和城乡建设局网站,网站建设制作设计公司,网站建设项目概要设计方案,电商网站建设推荐目录
题目描述#xff1a;
解法一#xff1a;递归法
解法二#xff1a;迭代法
解法三#xff1a;Morris遍历 二叉树的后序遍历
题目描述#xff1a;
给你一棵二叉树的根节点 root #xff0c;返回其节点值的 后序遍历 。 示例 1#xff1a; 输入#xff1a;root …目录
题目描述
解法一递归法
解法二迭代法
解法三Morris遍历 二叉树的后序遍历
题目描述
给你一棵二叉树的根节点 root 返回其节点值的 后序遍历 。 示例 1 输入root [1,null,2,3]
输出[3,2,1]
示例 2
输入root []
输出[]示例 3
输入root [1]
输出[1]提示
树中节点的数目在范围 [0, 100] 内-100 Node.val 100
解法一递归法 ListInteger res new ArrayList();public ListInteger postorderTraversal(TreeNode root) {if(root null){return res;}postorderTraversal(root.left);postorderTraversal(root.right);res.add(root.val);return res;}
复杂度分析
时间复杂度O(n)O(n)其中 nn 是二叉搜索树的节点数。每一个节点恰好被遍历一次。空间复杂度O(n)O(n)为递归过程中栈的开销平均情况下为 O(\log n)O(logn)最坏情况下树呈现链状为 O(n)O(n)。
解法二迭代法 public ListInteger postorderTraversal1(TreeNode root) {ListInteger res new ArrayList();if(root null){return res;}DequeTreeNode stack new ArrayDeque();TreeNode cur root;TreeNode prev null;while(cur!null || !stack.isEmpty()){while(cur ! null){stack.push(cur);cur cur.left;}cur stack.pop();if(cur.rightnull || prevcur.right){res.add(cur.val);prev cur;cur null;}else{stack.push(cur);cur cur.right;}}return res;}
复杂度分析
时间复杂度O(n)O(n)其中 nn 是二叉搜索树的节点数。每一个节点恰好被遍历一次。空间复杂度O(n)O(n)为迭代过程中显式栈的开销平均情况下为 O(\log n)O(logn)最坏情况下树呈现链状为 O(n)O(n)。
解法三Morris遍历 public ListInteger postorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();if (root null) {return res;}TreeNode p1 root, p2 null;while (p1 ! null) {p2 p1.left;if (p2 ! null) {while (p2.right ! null p2.right ! p1) {p2 p2.right;}if (p2.right null) {p2.right p1;p1 p1.left;continue;} else {p2.right null;addPath(res, p1.left);}}p1 p1.right;}addPath(res, root);return res;}public void addPath(ListInteger res, TreeNode node) {int count 0;while (node ! null) {count;res.add(node.val);node node.right;}int left res.size() - count, right res.size() - 1;while (left right) {int temp res.get(left);res.set(left, res.get(right));res.set(right, temp);left;right--;}}
复杂度分析
时间复杂度O(n)O(n)其中 nn 是二叉树的节点数。没有左子树的节点只被访问一次有左子树的节点被访问两次。空间复杂度O(1)O(1)。只操作已经存在的指针树的空闲指针因此只需要常数的额外空间。
