上篇已经了解对二叉树有了大概了解,本篇学习二叉树的前序、中序、后序及层序遍历的递归与非递归共7种遍历方法,快收藏吧~
目录
1、前序遍历
递归方式:
迭代方式:
2、中序遍历
递归方式:
迭代方式:
3、后序遍历:
递归方式
迭代方式:
4、层序遍历
递归方式
迭代方式:
二叉树的前序、中序、后序及层序遍历的递归与非递归遍历方法
遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结 点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如:打印节点内容、节点内容加 1)。 遍历是二叉树上最重要的操作之一,是二叉树上进行其它运算之基础。
二叉树的遍历方法有以下四种 :
- 先序遍历(根左右)
首先访问根结点,然后递归地遍历左子树,最后遍历右子树。例如对于二叉树:先序遍历的结果为:1->2->4->8->9->5->10->11->3->6->7。
- 中序遍历(左根右)
首先遍历左子树,然后访问根结点,最后遍历右子树。例如对于二叉树:中序遍历的结果为:8->4->9->2->10->5->11->1->6->3->7。
- 后序遍历(左右根)
首先遍历左子树,然后遍历右子树,最后访问根结点。例如对于二叉树:后序遍历的结果为:8->9->4->10->11->5->2->6->7->3->1。
- 层序遍历
自上而下,自左至右逐层访问树的结点的过程就是层序遍历。
它是按广度优先搜索的策略,从根结点出发,依次访问每一层上的节点。这种策略在实际应用中使用较多,如在计算机图形学中用于渲染场景图等。例如对于二叉树:层次遍历的结果为:1->2->3->4->5->6->7->8->9->10->11
下面讲解代码,前序遍历、中序遍历和后序遍历的简单递归方法不附图讲解,主要解释它们的迭代方式及层序遍历
1、前序遍历
递归方式:
定义 preorder(root) 表示当前遍历到 root 节点的答案。按照定义,我们只要首先将 root 节点的值加入答案,然后递归调用 preorder(root.left) 来遍历 root 节点的左子树,最后递归调用 preorder(root.right) 来遍历 root 节点的右子树即可,递归终止的条件为碰到空节点。
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();preorder(root, res);return res;}public void preorder(TreeNode root, List<Integer> res) {if (root == null) {return;}res.add(root.val);preorder(root.left, res);preorder(root.right, res);}
}
复杂度分析
时间复杂度:O(n),其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。
空间复杂度:O(n),为递归过程中栈的开销,平均情况下为 O(logn),最坏情况下树呈现链状,为 O(n)。
迭代方式:
迭代的方式实现方法一的递归函数,两种方式是等价的,区别在于递归的时候隐式地维护了一个栈,而我们在迭代的时候需要显式地将这个栈模拟出来,其余的实现与细节都相同,具体可以参考下面的代码。
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if(root==null) return res;Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){TreeNode p = stack.pop();res.add(p.val);if(p.right!=null)stack.push(p.right);if(p.left!=null)stack.push(p.left);}return res;}
}
注释: 先将root压栈,进入 while 循环,每循环一次栈顶出栈一次并记录该结点,将其左结点右结点压栈,栈为空退出循坏。
时间复杂度:O(n),其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。
空间复杂度:O(n),为迭代过程中显式栈的开销,平均情况下为 O(logn),最坏情况下树呈现链状,为 O(n)。
2、中序遍历
递归方式:
定义 inorder(root) 表示当前遍历到 root 节点的答案,那么按照定义,我们只要递归调用 inorder(root.left) 来遍历 root 节点的左子树,然后将 root 节点的值加入答案,再递归调用inorder(root.right) 来遍历 root 节点的右子树即可,递归终止的条件为碰到空节点。
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();inorder(root, res);return res;}public void inorder(TreeNode root, List<Integer> res) {if (root == null) {return;}inorder(root.left, res);res.add(root.val);inorder(root.right, res);}
}
复杂度分析
时间复杂度:O(n),其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
空间复杂度:O(n)。空间复杂度取决于递归的栈深度,而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别
迭代方式:
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();Stack<TreeNode> stack = new Stack<>();while (root != null || !stack.isEmpty()) {while (root != null) {stack.push(root);root = root.left;}root = stack.pop();res.add(root.val);root = root.right;}return res;}
}
子循环中root遍历到root左子树最深层次过程中,依次将左结点压栈,左结点为空退出子循环,将栈顶元素出栈, root=root.right重新进入大循环既可遍历该树所有结点。
时间复杂度:O(n),其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
空间复杂度:O(n)。空间复杂度取决于栈深度,而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。
3、后序遍历
递归方式
定义 postorder(root) 表示当前遍历到 root 节点的答案。按照定义,我们只要递归调用 postorder(root->left) 来遍历 root 节点的左子树,然后递归调用 postorder(root->right) 来遍历 root 节点的右子树,最后将 root 节点的值加入答案即可,递归终止的条件为碰到空节点。
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();postorder(root, res);return res;}public void postorder(TreeNode root, List<Integer> res) {if (root == null) {return;}postorder(root.left, res);postorder(root.right, res);res.add(root.val);}
}
复杂度分析
时间复杂度:O(n),其中 n 是二叉搜索树的节点数。每一个节点恰好被遍历一次。
空间复杂度:O(n),为递归过程中栈的开销,平均情况下为 O(logn),最坏情况下树呈现链状,为 O(n)。
迭代方式:
我们也可以用迭代的方式实现方法一的递归函数,两种方式是等价的,区别在于递归的时候隐式地维护了一个栈,而我们在迭代的时候需要显式地将这个栈模拟出来,其余的实现与细节都相同,具体可以参考下面的代码(为了更好的注释,代码放入块引用中)
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
Stack <TreeNode> stack = new Stack<>();
TreeNode prev = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.peek();// 取栈顶元素
//因为是后序遍历,当前结点有无右结点决定它是否打印
//所以取出栈顶元素,判断有无右结点
//而打印当前结点情况分为两种,1、该结点无右结点 2、该结点的右结点已遍历
if (root.right == null || root.right == prev) {
res.add(root.val);
stack.pop();
prev = root;//用prev指向root,表示已被遍历
root = null;
} else
root = root.right;
}
return res;
}
}
如上图情况,若if条件语句不判断 D.right ( K )是否被上次遍历则会陷入K出栈压栈无限循环中
复杂度分析
时间复杂度:O(n),其中 n 是二叉搜索树的节点数。每一个节点恰好被遍历一次。
空间复杂度:O(n),为迭代过程中显式栈的开销,平均情况下为 O(logn),最坏情况下树呈现链状,为 O(n)。
4、层序遍历
即逐层地,从左到右访问所有节点。
递归方式
class Solution {List<List<Integer>> result=new ArrayList<>();public List<List<Integer>> levelOrder(TreeNode root) {order(root,0);return result;}public void order(TreeNode node,int deep){if(node==null)return;deep++;if(result.size()<deep){List<Integer> item=new ArrayList<>();result.add(item);}result.get(deep-1).add(node.val);order(node.left,deep);order(node.right,deep);}
}
在方法void order(TreeNode node,int deep) ,传相应的结点和二维数组下标,设置节点对应位置
加图理解:
时间复杂度;O(n)
迭代方式:
代码设计重点:出栈既遍历。在结点出栈时,同时将不为空的左右结点入栈。进入子循环前,用size记录栈内元素,进入子循环后,依次将栈顶元素弹出,同时将不为空的左右结点入,size--;
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res=new ArrayList<>();if(root==null)return res;Queue<TreeNode> queue=new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){int size=queue.size();List<Integer> list=new ArrayList<>();while(size--!=0){TreeNode top=queue.poll();list.add(top.val);if(top.left!=null)queue.offer(top.left);if(top.right!=null)queue.offer(top.right);}res.add(list);}return res;}
}
时间复杂度;O(n)
二叉树的遍历结束