招代理商的网站,住房建设建设部网站,网站建设的理念,移动端网站 优帮云【问题描述】[]
前序遍历 先输出当前结点的数据#xff0c;再依次遍历输出左结点和右结点 中序遍历 先遍历输出左结点#xff0c;再输出当前结点的数据#xff0c;再遍历输出右结点 后续遍历 先遍历输出左结点#xff0c;再遍历输出右结点#xff0c;最后输出当前结点的数…【问题描述】[]
前序遍历 先输出当前结点的数据再依次遍历输出左结点和右结点 中序遍历 先遍历输出左结点再输出当前结点的数据再遍历输出右结点 后续遍历 先遍历输出左结点再遍历输出右结点最后输出当前结点的数据 【解答思路】
递归 /迭代栈 时间复杂度O(N) 空间复杂度O(N)
1. 前序遍历
1.1 递归 二叉树遍历前序、中序、后序的递归方法唯一改变的是记录节点值操作的位置
class Solution {public ListInteger preorderTraversal(TreeNode root) {if (root ! null) {res.add(root.val);preorderTraversal(root.left);preorderTraversal(root.right);}return res;}
}
1.2 迭代栈 需要一个辅助栈
class Solution {
public ListInteger preorderTraversal(TreeNode root) {ListInteger list new ArrayList();StackTreeNode stack new Stack();TreeNode cur root;while (cur ! null || !stack.isEmpty()) {while (cur ! null) {//立马加入当前值list.add(cur.val);stack.push(cur);cur cur.left; //考虑左子树}//节点为空就出栈cur stack.pop();//考虑右子树cur cur.right;}return list;
}}
2. 中序遍历
1.1 递归 二叉树遍历前序、中序、后序的递归方法唯一改变的是记录节点值操作的位置
class Solution {ListInteger res new ArrayList();public ListInteger inorderTraversal(TreeNode root) {if (root ! null) {inorderTraversal(root.left);res.add(root.val);inorderTraversal(root.right);}return res;}
}
1.2 迭代栈 需要一个辅助栈
public ListInteger inorderTraversal(TreeNode root) {ListInteger ans new ArrayList();StackTreeNode stack new Stack();TreeNode cur root;while (cur ! null || !stack.isEmpty()) {//节点不为空一直压栈while (cur ! null) {stack.push(cur);cur cur.left; //考虑左子树}//节点为空就出栈cur stack.pop();//当前值加入ans.add(cur.val);//考虑右子树cur cur.right;}return ans;
}作者windliang
链接https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--34/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
3. 后序遍历
1.1 递归 二叉树遍历前序、中序、后序的递归方法唯一改变的是记录节点值操作的位置
class Solution {ListInteger res new ArrayList();public ListInteger postorderTraversal(TreeNode root) {if (root ! null) {postorderTraversal(root.left);postorderTraversal(root.right);res.add(root.val);}return res;}
}
1.2 迭代栈 需要两个辅助栈 -从根节点开始依次迭代弹出栈顶元素输出到输出列表中然后依次压入它的所有孩子节点按照从上到下、从左至右的顺序依次压入栈中。
-因为深度优先搜索后序遍历的顺序是从下到上、从左至右所以需要将输出列表逆序输出。
class Solution {ListInteger res new ArrayList();public ListInteger postorderTraversal(TreeNode root) {if (root null) {return res;}LinkedListTreeNode stack new LinkedList();LinkedListTreeNode stackTemp new LinkedList();stackTemp.push(root);while (!stackTemp.isEmpty()) {TreeNode curNode stackTemp.pop();//stack压入stack.push(curNode);if (curNode.left ! null) {stackTemp.push(curNode.left);}if (curNode.right ! null) {stackTemp.push(curNode.right);}}//逆序while (!stack.isEmpty()) {res.add(stack.pop().val);}return res;}
}
1.3 转换思想 后续转前序 逆转 后序遍历的顺序是 左 - 右 - 根。 前序遍历的顺序是 根 - 左 - 右 左右其实是等价的所以我们也可以轻松的写出 根 - 右 - 左 的代码。 然后把 根 - 右 - 左 逆序就是 左 - 右 - 根也就是后序遍历了。 public ListInteger postorderTraversal2(TreeNode root) {ListInteger list new ArrayList();StackTreeNode stack new Stack();TreeNode cur root;while (cur ! null || !stack.isEmpty()) {if (cur ! null) {list.add(cur.val);stack.push(cur);cur cur.right; // 考虑右子树} else {// 节点为空就出栈cur stack.pop();// 考虑左子树cur cur.left;}}//翻转Collections.reverse(list);return list;
}
1.4 一个栈
public ListInteger postorderTraversal(TreeNode root) {if (root null) return new ArrayListInteger();TreeNode node root;ListInteger ret new ArrayListInteger();StackTreeNode stack new StackTreeNode();while(node ! null || !stack.isEmpty()) {while (node ! null) {stack.push(node);node node.left;}node stack.pop();// 后序遍历// 如果没有右孩子或者右孩子被访问过了 {Alex Zheng 感谢建议哈}if (node.right null || (ret.size() ! 0 ret.get(ret.size() - 1).equals(node.right.val)) ) {ret.add(node.val);node null;} else {stack.push(node);node node.right;}}return ret;}链接https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/bian-li-tong-jie-by-long_wotu/
【总结】
1. 前中后序遍历变化的是[中]的位置左到右的顺序不改变
前序遍历 中左右中序遍历 左中右后续遍历 左右中
2.pop 与 poll 都是取出 LinkedList 的第一个元素并将该元素删除等效于removeFirst
不同点两者的实现所用数据结构不同
poll 是基于队列结构实现的方法当队列中没有元素时调用该方法返回 nullpop 是基于栈结构实现的方法当栈中没有元素时调用该方法会发生异常
3. 递归模板 res.add(root.val); 位置动态变化 public ListInteger preorderTraversal(TreeNode root) {if (root ! null) {//先序遍历 res.add(root.val);preorderTraversal(root.left);//中序遍历 res.add(root.val);preorderTraversal(root.right);//后序遍历 res.add(root.val);}return res;}4. 迭代模板 list.add(cur.val);位置动态变化 前中序可遍历后续遍历可由前序遍历修改后逆转 public ListInteger preorderTraversal(TreeNode root) {ListInteger list new ArrayList();StackTreeNode stack new Stack();TreeNode cur root;while (cur ! null || !stack.isEmpty()) {while (cur ! null) {stack.push(cur);// 先序遍历 list.add(cur.val);cur cur.left; }//节点为空就出栈cur stack.pop();// 中序序遍历 list.add(cur.val);cur cur.right;//后序遍历 list.add(cur.val); 需要变得多}return list;
}
参考链接:https://leetcode.wang/leetcode-145-Binary-Tree-Postorder-Traversal.html
