算法(八) 二叉树遍历
二叉树遍历
- 前序遍历 根 + 左 + 右
- 中序遍历 左 + 中 + 右
- 后序遍历 左 + 右 + 中
- 层序遍历 来自leetcode102，方法主要用广搜或队列，就不在这里写了。
- 二叉树遍历一般就是递归和非递归
1，递归
简单，但是一般面试不考。都是用迭代的。
前序遍历
来自LeetCode144
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
traversal(root,res);
return res;
}
public void traversal(TreeNode cur,List<Integer> res){
if(cur == null)
return;
res.add(cur.val);
traversal(cur.left,res);
traversal(cur.right,res);
}
}中序遍历
来自LeetCode94
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
traversal(root,res);
return res;
}
public void traversal(TreeNode cur,List<Integer> res){
if(cur == null)
return;
traversal(cur.left,res);
res.add(cur.val);
traversal(cur.right,res);
}
}后序遍历
来自LeetCode145
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
traversal(root,res);
return res;
}
public void traversal(TreeNode cur,List<Integer> res){
if(cur == null)
return;
traversal(cur.left,res);
traversal(cur.right,res);
res.add(cur.val);
}
}2，非递归/迭代
前序遍历
运用栈存入，出栈时存入该节点的左右节点。
注意的是栈的特性，所以应该先传入right再传入左。
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
if( cur == null)
return list;
stack.push(cur);
while(!stack.isEmpty()){
cur = stack.pop();
list.add(cur.val);
if(cur.right!=null) stack.push(cur.right);
if(cur.left!=null) stack.push(cur.left);
}
return list;
}
}
中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<TreeNode>();
while(cur!=null||!stack.isEmpty()){
if(cur!=null){
stack.push(cur);
cur = cur.left;
}
else{
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
}
return list;
}
}简称为左链入栈，就是左链先全部入栈，最后考虑右节点的情况。
记牢！！！！！！！！！！！！！！！！！
后序遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if(root == null)
return list;
TreeNode cur = root;
TreeNode pre = null;
Stack<TreeNode> stack = new Stack<TreeNode>();
while(cur!=null||!stack.isEmpty()){
while(cur!=null){
stack.push(cur);
cur = cur.left;
}
cur = stack.peek();
if(cur.right==null||cur.right==pre){
pre = stack.pop();
list.add(pre.val);
cur = null;
}else{
cur = cur.right;
}
}
return list;
}
}其实和中序遍历差不多。更难写。
特殊方法：Morris 遍历
将空间复杂度从O(n)变成O(1)。
有空再实现吧
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-08-20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录