前言(背景):
最近在简单的回顾数据结构的相关知识。这里简单的记录一下,关于二叉树的遍历:递归和迭代。
树结构
public class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(int x){
val=x;
}
}
递归方案(前、中、后)
递归方法很简单,这里就直接记录下代码。
前序:上、左、右
List<Integer> list=new ArrayList<Integer>();
pubilc void preorderTraversal(TreeNode root){
if(root == null) return;
list.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
}
中序:左、上、右
List<Integer> list=new ArrayList<Integer>();
pubilc void inorderTraversal(TreeNode root){
if(root == null) return;
preorderTraversal(root.left);
list.add(root.val);
preorderTraversal(root.right);
}
后序:左、右、上
List<Integer> list=new ArrayList<Integer>();
pubilc void postorderTraversal(TreeNode root){
if(root == null) return;
preorderTraversal(root.left);
preorderTraversal(root.right);
list.add(root.val);
}
非递归方案:迭代遍历(前、中、后)
前序:上、左、右
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null) return res;
Deque<TreeNode> stack = new LinkedList<TreeNode>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
//必须先入栈右孩子节点,才能后出栈
if(node.right != null){
stack.push(node.right);
}
//必须后入栈左孩子节点,才能先出栈
if(node.left != null){
stack.push(node.left);
}
//上、左、右
res.add(node.val);
}
return res;
}
注:这里的前序遍历迭代的实现,是通过堆栈进行“上、左、右”的遍历。可以联想如果遍历时,顺序是“上、右、左”,遍历完后再进行倒序成“左、右、上”,这就是后序迭代的逻辑了。
中序:左、上、右
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode cur = root;
while (!stack.isEmpty() || cur != null) {
//这里可以保证直接到最左部的叶子节点
while (cur != null) {
stack.push(cur);
//位置1
cur = cur.left;
}
//到了左部叶子节点后开始回溯:左、上、右
cur = stack.pop();
//记录当前节点
//位置2
res.add(cur.val);
//右孩子,即使为空也进入
cur = cur.right;
}
return res;
}
注:通过中序迭代的逻辑,应该可以看出,将“位置2”的一句代码,移到“位置1”,则此代码变成前序遍历的实现。
后序:左、右、上
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null) return res;
Deque<TreeNode> stack = new LinkedList<TreeNode>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
//为了保证遍历顺序是上、右、左。左孩子节点先入栈
if(node.left != null){
stack.push(node.left);
}
//右孩子节点后入栈
if(node.right != null){
stack.push(node.right);
}
//插入位置并非动态数组的末尾,而是动态数组的开头
//如果正常插入,则此种方法的顺序是:上、右、左
//这里相当于进行了倒序
res.add(0,node.val);
}
return res;
}
注:这里与本文前序遍历不同之处有两点:
1、左右孩子节点入栈顺序相反。
2、是list.add()方法的使用不同。
层序遍历(迭代实现)
public List<Integer> levelOrderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null) return res;
//层序遍历使用队列实现
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
//非空左孩子入队
if(node.left != null){
queue.offer(node.left);
}
//非空右孩子入队
if(node.right != null){
queue.offer(node.right);
}
//记录当前节点
res.add(node.val);
}
return res;
}
最后的备注:
1、对于Java而言,集合类并没有单独的Stack接口,只是出于兼容性考虑,遗留了Stack类。
2、而对于编程者而言最好持有接口来引用某个实现类,而非直接持有对象本身。这是因为持有接口说明代码的抽象层次更高,而且接口本身定义的方法代表了特定的用途。
所以综上,在需要使用Stack类时,最好使用Deque接口来“模拟”一个Stack。
当我们把Deque作为Stack使用时,注意只调用push()、pop()、peek()方法。而不要调用addFirst()、removeFirst()、peekFirst()方法,破坏堆栈本质。
注:
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名,转载请标明出处。