网站广告位投放,宿迁经济技术开发区属于哪个区,徐州高端模板建站,新网站怎么做排名目录 建议先刷一下中序遍历 题目地址#xff1a; 题目#xff1a; 我们直接看题解吧#xff1a; 解题方法#xff1a; 注#xff1a; 解题分析#xff1a; 解题思路#xff1a; 代码实现#xff1a; 代码实现#xff08;递归#xff09;#xff1a; 代码实现#x…目录 建议先刷一下中序遍历 题目地址 题目 我们直接看题解吧 解题方法 注 解题分析 解题思路 代码实现 代码实现递归 代码实现迭代 建议先刷一下中序遍历 二叉树的中序遍历力扣-CSDN博客 题目地址 145. 二叉树的后序遍历 - 力扣LeetCode 难度简单 今天刷二叉树的后序遍历大家有兴趣可以点上看看题目要求试着做一下。
题目
给你一棵二叉树的根节点 root 返回其节点值的 后序遍历 。 我们直接看题解吧 解题方法 方法1、递归 方法2、迭代 方法3、Morris 注 有一种巧妙的方法可以在线性时间内只占用常数空间来实现后序遍历。这种方法由 J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」中首次提出因此被称为 Morris 遍历。 Morri遍历的核心思想是利用树的大量空闲指针实现空间开销的极限缩减 解题分析 ·后序遍历顺序左子树-右子树-根节点即左右根 ·递归方法虽易懂但效率偏低迭代方法虽效率高但不易理解 因此这里着重讲一下Morris方法。 解题思路 1、新建临时节点令该节点为 root 2、如果当前节点的左子节点为空则遍历当前节点的右子节点 3、如果当前节点的左子节点不为空在当前节点的左子树中找到当前节点在中序遍历下的前驱节点 · 如果前驱节点的右子节点为空将前驱节点的右子节点设置为当前节点当前节点更新为当前节点的左子节点。 ·如果前驱节点的右子节点为当前节点将它的右子节点重新设为空。倒序输出从当前节点的左子节点到该前驱节点这条路径上的所有节点。当前节点更新为当前节点的右子节点。 4、重复步骤 2 和步骤 3直到遍历结束。 具体题解可参考-145. 二叉树的后序遍历题解 代码实现
class Solution {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--;}}
}
代码实现递归
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();postorder(root, res);return res;}public void postorder(TreeNode root, ListInteger res) {if (root null) {return;}postorder(root.left, res);postorder(root.right, res);res.add(root.val);}
}
代码实现迭代
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();if (root null) {return res;}DequeTreeNode stack new LinkedListTreeNode();TreeNode prev null;while (root ! null || !stack.isEmpty()) {while (root ! null) {stack.push(root);root root.left;}root stack.pop();if (root.right null || root.right prev) {res.add(root.val);prev root;root null;} else {stack.push(root);root root.right;}}return res;}
}
