本文提供二叉树 前中序 三种遍历方式的 递归和迭代 统一写法。递归写法很简单
在面试中不足以获得面试官的青睐，应该重点掌握迭代写法
144. 二叉树的前序遍历
94 . 二叉树的中序遍历
145. 二叉树的后序遍历
有两种通用的遍历树的策略：
深度优先搜索（DFS）
在这个策略中，我们采用深度作为优先级，以便从跟开始一直到达某个确定的叶子，
然后再返回根到达另一个分支。
深度优先搜索策略又可以根据根节点、左孩子和右孩子的相对顺序
被细分为前序遍历，中序遍历和后序遍历。
宽度优先搜索（BFS）
我们按照高度顺序一层一层的访问整棵树，高层次的节点将会比低层次的节点先被访问到。
对应数的层次(层序遍历)
*****五星重点
我要评论/*
* Return true if there is a path from cur to target.
*/
boolean DFS(Node cur, Node target, Set<Node> visited) {
return true if cur is target;
for (next : each neighbor of cur) {
if (next is not in visited) {
add next to visted;
return true if DFS(next, target, visited) == true;
}
}
return false;
}
/*
* Return true if there is a path from cur to target.
*/
boolean DFS(int root, int target) {
Set<Node> visited;
Stack<Node> s; //额外注意：BFS 这里使用的是queue队列。
add root to s;
while (s is not empty) {
Node cur = the top element in s;
return true if cur is target;
for (Node next : the neighbors of cur) {
if (next is not in visited) {
add next to s;
add next to visited;
}
}
remove cur from s;
}
return false;
}
链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/er-cha-shu-de-qian-xu-
递归写法只需要调整list添加节点值 和 左右子树递归的顺序即可。
前序： 根 左 右 ：list.add(root.val) -> dfs(左子树) -> dfs(右子树)
中序： 左 根 右 ：dfs(左子树) -> list.add(root.val) -> dfs(右子树)
后序： 左 右 根 ：dfs(左子树) -> dfs(右子树) -> list.add(root.val)
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
//创建list
List<Integer> res = new ArrayList();
//递归调用
dfs(root,res);
//返回结果
return res;
}
private void dfs(TreeNode root, List<Integer> list){
if(root != null ){
//1.先添加root值
list.add(root.val);
//2.递归左子树
dfs(root.left,list);
//3.递归右子树
dfs(root.right,list);
}
/* 【另一种写法】
//递归终止条件， base case
if(root == null) return;
//先遍历根节点， 直接添加节点值
list.add(root.val);//前序遍历 根 左 右
//递归左子树
//if(root.left != null)
recur(root.left,list);
//递归右子树
//if(root.right != null)
recur(root.right,list);
*/
}
}
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
//创建list
List<Integer> res = new ArrayList();
//递归调用
dfs(root,res);
//返回结果
return res;
}
private void dfs(TreeNode root, List<Integer> list){
if(root != null ){
//1.递归左子树
dfs(root.left,list);
//2.添加root值
list.add(root.val);
//3.递归右子树
dfs(root.right,list);
}
/* 【另一种写法】
//递归终止条件， base case
if(root == null) return;
//递归左子树
//if(root.left != null)
recur(root.left,list);
//遍历根节点， 直接添加节点值
list.add(root.val);//前序遍历 根 左 右
//递归右子树
//if(root.right != null)
recur(root.right,list);
*/
}
}
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
//创建list
List<Integer> res = new ArrayList();
//递归调用
dfs(root,res);
//返回结果
return res;
}
private void dfs(TreeNode root, List<Integer> list){
if(root != null ){
//1.递归左子树
dfs(root.left,list);
//2.递归右子树
dfs(root.right,list);
//3.添加root值
list.add(root.val);
}
/* 【另一种写法】
//递归终止条件， base case
if(root == null) return;
//递归左子树
//if(root.left != null)
recur(root.left,list);
//递归右子树
//if(root.right != null)
recur(root.right,list);
//遍历根节点， 直接添加节点值
list.add(root.val);//前序遍历 根 左 右
*/
}
}
前序遍历 标准的前序遍历的dfs显示调用栈的写法。(虽然这种写法很常见，但是无法中后序统一起来)
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
//递归写法 DFS + stack 和 BFS + queue的写法 很像
LinkedList<Integer> res = new LinkedList();
//LinkedList 可以当做stack 和 deque 双端队列使用
// java 中的 stack 栈 已经被LinkedList 取代了。
LinkedList<TreeNode> stack = new LinkedList();
if(root == null) return res;//leetcode这里必须返回空集合，不能返回null
stack.add(root);
//dfs
while(!stack.isEmpty()){
//创建当前节点
TreeNode curr = stack.pollLast();// poll删除头部元素
//res 添加节点值
res.add(curr.val);
//stack添加curr的临近节点(左右子树)
//添加右子树 注意是右子树， 先进后出
if(curr.right != null) stack.add(curr.right);
//添加左子树节点
if(curr.left != null) stack.add(curr.left);
}
//返回结果
return res;
}
}
中序遍历：中序遍历需要先让指针找到每颗子树的最最下角。
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
LinkedList<Integer> res = new LinkedList();
LinkedList<TreeNode> stack = new LinkedList();
TreeNode curr = root;
while( curr != null || !stack.isEmpty()){
//先判断root.left 是否为空
if(curr != null){
//不为空 stack 添加节点
stack.add(curr);
//curr指向左节点
curr = curr.left;
}else{
//如果curr.left为空 就添加curr到res
curr = stack.pollLast();
res.add(curr.val);
//curr 指向右节点
curr = curr.right;
}
}
return res;
}
}
后序遍历 可以在前序遍历基础上修改一行得到：res.addFirst(curr.val); 这种解只是能返回遍历的结果，并不是严格意义上树拓扑结构的遍历。虽然结果是正确，但是如果需要按照后续遍历的顺序对树节点进行访问（或操作），此解法就无法满足。不过也可视为一种巧妙的解题方法。
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
//递归写法 DFS + stack 和 BFS + queue的写法 很像
LinkedList<Integer> res = new LinkedList();
//LinkedList 可以当做stack 和 deque 双端队列使用
// java 中的 stack 栈 已经被LinkedList 取代了。
LinkedList<TreeNode> stack = new LinkedList();
if(root == null) return res;//leetcode这里必须返回空集合，不能返回null
stack.add(root);
//dfs
while(!stack.isEmpty()){
//创建当前节点
TreeNode curr = stack.pollLast();// poll删除头部元素
//res 添加节点值
res.addFirst(curr.val); //注意：添加的链表的头部
//stack添加curr的临近节点(左右子树)
//添加右子树 注意是右子树， 先进后出
if(curr.right != null) stack.add(curr.right);
//添加左子树节点
if(curr.left != null) stack.add(curr.left);
}
//返回结果
return res;
}
}
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
//创建res 和 stack
LinkedList<Integer> res = new LinkedList();
LinkedList<TreeNode> stack = new LinkedList();
//异常处理
if(root == null) return res;
//stack 初始化 根节点先入栈
stack.add(root);
while(!stack.isEmpty()){
//创建当前节点 stack弹出节点并判断是否访问过
TreeNode curr = stack.pollLast();
//非空说明没有访问过，然后右节点入栈，左节点入栈，最后根节点入栈，最后压入一个空节点(重要)
if( curr !=null){
if(curr.right != null) stack.add(curr.right);//先入栈右节点
if(curr.left != null) stack.add(curr.left);//然后入栈左节点
stack.add(curr);//再入栈当前节点
stack.add(null);//最后入栈一个空节点 空节点是一个标识，标识当前节点已经被放翁，但是还没有处理 （重要~！）
}else{
//如果弹出的节点为空节点，表明当前栈顶节点已经访问过
res.add(stack.pollLast().val);//
}
}
//返回结果
return res;
}
}
class Solution {
public static List<Integer> inorderTraversal(TreeNode root) {
//创建res 和stack
LinkedList<Integer> res = new LinkedList();
LinkedList<TreeNode> stack = new LinkedList();
//特例处理
if(root == null) return res;
//初始化 stack root 节点入栈
stack.add(root);
//dfs遍历
while(!stack.isEmpty()){
//创建当前节点 stack出栈
TreeNode curr = stack.pollLast();
//判断curr 是否为空，不为空就没有被访问过
//先添加右节点，然后添加curr节点， 再添加一个空节点，最后添加左节点
if(curr != null) {
if (curr.right != null) stack.add(curr.right);
stack.add(curr);
stack.add(null);//添加null 作为一个表示。表示已经访问过，但是还没有被处理
if (curr.left != null) stack.add(curr.left);
}else{
//curr == null 说明已经被访问过
res.add(stack.pollLast().val);
}
}
//返回结果
return res;
}
}
class Solution {
public static List<Integer> inorderTraversal(TreeNode root) {
//创建res 和stack
LinkedList<Integer> res = new LinkedList();
LinkedList<TreeNode> stack = new LinkedList();
//特例处理
if(root == null) return res;
//初始化 stack root 节点入栈
stack.add(root);
//dfs遍历
while(!stack.isEmpty()){
//创建当前节点 stack出栈
TreeNode curr = stack.pollLast();
//判断curr 是否为空，不为空就没有被访问过
//添加curr节点，然后添加一个空节点，再添加右节点，最后添加左节点
if(curr != null) {
stack.add(curr);
stack.add(null);//添加null 作为一个表示。表示已经访问过，但是还没有被处理
if (curr.right != null) stack.add(curr.right);
if (curr.left != null) stack.add(curr.left);
}else{
//curr == null 说明已经被访问过
res.add(stack.pollLast().val);
}
}
//返回结果
return res;
}
}
递归算法复杂度
时间复杂度：O(n)。递归函数 T(n) = 2 *T(n/2)+1。
空间复杂度：最坏情况下需要空间O(n)，平均情况为O(logn)。
迭代算法复杂度
时间复杂度：访问每个节点恰好一次，时间复杂度为 O(N) ，其中 NN 是节点的个数，也就是树的大小。
空间复杂度：取决于树的结构，最坏情况存储整棵树，因此空间复杂度是 O(N)。
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/er-cha-shu-de-hou-xu-bian-li-by-leetcode/
public class Solution {
//层序遍历 BFS + queue
public List<List<Integer>> levelOrder(TreeNode root) {
LinkedList<List<Integer>> res = new LinkedList();
LinkedList<TreeNode> queue = new LinkedList();
//特例处理
if(root == null) return res;
//初始化queue
queue.add(root);
while(!queue.isEmpty()) {
//这里需要额外记录下queue 的大小，主要为了处理完一层的节点后，方便返回一个List<Integer>
int n = queue.size();
List<Integer> level = new LinkedList<>();
//将当前队列的中的所有节点 向四周扩散
for(int i = 0 ; i < n; i++){
TreeNode curr = queue.pollFirst();
level.add(curr.val); //先将当前节点条件到list
if(curr.left != null) queue.add(curr.left);
if(curr.right!= null) queue.add(curr.right);
}
res.add(level);
}
return res;
}
}
本文地址：https://blog.csdn.net/lightupworld/article/details/107458449
如对本文有疑问， 点击进行留言回复！！
浅谈Java如何实现一个基于LRU时间复杂度为O(1)的缓存
JDK1.6“新“特性Instrumentation之JavaAgent(推荐)
before社区电量是什么意思 Before社区电量获得方法
网友评论