0%

树的前中后序层次遍历（递归、迭代、莫里斯算法）

发表于 分类于 阅读次数：
本文字数： 阅读时长 ≈

有两种通用的遍历树的策略：

  1. 深度优先搜索（DFS）：从根开始一直到达某个确定的叶子，然后再返回根到达另一个分支。

    深度优先搜索策略又可以根据根节点、左孩子和右孩子的相对顺序被细分为前序遍历，中序遍历和后序遍历。一般用栈来实现

  2. 宽度优先搜索（BFS）：我们按照高度顺序一层一层的访问整棵树，高层次的节点将会比低层次的节点先被访问到。一般用队列来实现

前序遍历（根-左-右）

递归版本

1
2
3
4
5
6
7
8
9
10
11
12
List < Integer > res = new ArrayList <> ();

public List<Integer> preorderTraversal(TreeNode root) {
	if(root!=null){
		res.add(root.val);
    	if(root.left!=null)
    		preorderTraversal(root.left);
    	if(root.right!=null)
    		preorderTraversal(root.right);
	}
	return res;
}

迭代算法版本1

因为栈是先进后出，所以先入右结点后入左结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<Integer>();
    if (root == null) {
        return res;
    }
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.add(node.val);
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
    return res;
}

迭代算法版本2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<Integer> preorderTraversal(TreeNode root) {
    List < Integer > res = new ArrayList <> ();
    Stack < TreeNode > stack = new Stack <> ();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
        	res.add(curr.val);
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        curr = curr.right;
    }
    return res;
}

莫里斯遍历

先看中序遍历的莫里斯遍历

Step 1: 将当前节点current初始化为根节点
Step 2: While current不为空
①若current没有左子节点
a. 将current添加到输出
b. 进入右子树，亦即, current = current.right
②否则进入current的左子树中，找到“右子节点为空或者即使不为空也要不等于当前节点”的最右侧节点

​ 如果最右侧结点为空，说明不是因为最右侧结点已经建立后继节点而退出while循环的

​ a. 将当前节点输出，并设置最右侧节点的右子节点（后继节点）为current
​ b. 进入左子树，亦即，current = current.left

​ ③如果最右侧结点的右子节点即后继节点已经指向current

​ a. 将最右侧节点的右子节点置空（恢复树结构，避免死循环）

​ b. 进入右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public List<Integer> preorderTraversal(TreeNode root) {
  LinkedList<Integer> output = new LinkedList<>();

  TreeNode node = root;
  while (node != null) {
    if (node.left == null) {
      output.add(node.val);
      node = node.right;
    }
    else {
      TreeNode predecessor = node.left;
      while ((predecessor.right != null) && (predecessor.right != node)) {
        predecessor = predecessor.right;
      }
      if (predecessor.right == null) {
        output.add(node.val);
        predecessor.right = node;
        node = node.left;
      }
      else{
        predecessor.right = null;//恢复树结构，避免死循环
        node = node.right;
      }
    }
  }
  return output;
}

参考LeetCode上的前序遍历的官方解答

中序遍历（左-根-右）

递归版本

1
2
3
4
5
6
7
8
9
10
11
12
List < Integer > res = new ArrayList <> ();

public List<Integer> inorderTraversal(TreeNode root) {
	if(root!=null){
    	if(root.left!=null)
    		inorderTraversal(root.left);
		res.add(root.val);
    	if(root.right!=null)
    		inorderTraversal(root.right);
	}
	return res;
}

迭代算法版本2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//若返回途中有右子树，则遍历该右子树，重复操作
    public List < Integer > inorderTraversal(TreeNode root) {
        List < Integer > res = new ArrayList < > ();
        Stack < TreeNode > stack = new Stack < > ();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            res.add(curr.val);
            curr = curr.right;
        }
        return res;
    }

莫里斯遍历

原理：线索二叉树

实现方法：

1
2
3
4
5
6
7
8
Step 1: 将当前节点current初始化为根节点
Step 2: While current不为空
		①若current没有左子节点
		a. 将current添加到输出
		b. 进入右子树，亦即, current = current.right
		②否则
		a. 在current的左子树中，令current成为最右侧节点的右子节点
		b. 进入左子树，亦即，current = current.left

对应代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List < Integer > inorderTraversal(TreeNode root) {
       List < Integer > res = new ArrayList < > ();
       TreeNode curr = root;
       TreeNode pre;
       while (curr != null) {
           if (curr.left == null) {
               res.add(curr.val);
               curr = curr.right; // 进入右子树
           } else { // 如果存在左子树
               pre = curr.left;
               while (pre.right != null) { // 找到左子树下的最右结点
                   pre = pre.right;
               }
               pre.right = curr; // 将最右结点的右子结点指向当前结点
               TreeNode temp = curr; // store cur node
               curr = curr.left; // 进入左子树
               temp.left = null; // original cur left be null, avoid infinite loops
           }
       }
       return res;
   }

参考LeetCode官方的解答中序遍历

后序遍历（左-右-根）

递归版本

1
2
3
4
5
6
7
8
9
10
11
12
List < Integer > res = new ArrayList <> ();

public List<Integer> postorderTraversal(TreeNode root) {
	if(root!=null){
    	if(root.left!=null)
    		postorderTraversal(root.left);
    	if(root.right!=null)
    		postorderTraversal(root.right);
		res.add(root.val);
	}
	return res;
}

迭代算法版本1

前序遍历顺序为：根 -> 左 -> 右

后序遍历顺序为：左 -> 右 -> 根

假设1： 将前序遍历顺序由从左到右修改为从右到左

那么结果链表就变为了：根 -> 右 -> 左

假设2： 在假设1的前提下，将前序遍历中节点插入结果链表尾部的逻辑，修改为将节点插入结果链表的头部

那么结果链表就变为了：左 -> 右 -> 根

这刚好是后序遍历的顺序

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<Integer>();
    if(root == null)
        return res;
    Stack<TreeNode> stack = new Stack<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;
}

迭代算法版本2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public List<Integer> postorderTraversal(TreeNode root) {
	List<Integer> list=new ArrayList<>();
	if(root ==null)
		return list;
	TreeNode visitedRight=null;
	Stack<TreeNode> stack=new Stack<>();
	while(root!=null || !stack.isEmpty()){
		while(root!=null){
			stack.push(root);
			root=root.left;
		}
        root=stack.peek();//while循环退出说明栈顶的是该子树的最左节点
        // 在不存在右节点或者右节点已经访问过的情况下，访问根节点
		if(root.right == null || root.right == visitedRight){
			list.add(root.val);
			stack.pop();
			visitedRight=root;
    		root=null;
		}
		else{
			root=root.right;
		}
	}
	return list;
}

莫里斯算法

结合 后序的迭代算法版本1 与 前序的莫里斯遍历 的思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new LinkedList();
    
    TreeNode node = root;
    TreeNode predecessor;
    
    while (node != null) {
        if (node.right == null) {
            result.add(0, node.val);
            node = node.left;
        } else {
            predecessor = node.right;
            while (predecessor.left != null && predecessor.left != node)
                predecessor = predecessor.left;
            
            if (predecessor.left == null) {
                result.add(0, node.val);
                predecessor.left = node;
                node = node.right;
            } else {
                predecessor.left = null;
                node = node.left;
            }
        }
    }
    
    return result;
}

参考LeetCode解答

层次遍历（BFS 队列）

不分行打印

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void BFSOrder(TreeNode root) {
	 if(root==null) return ;
	Queue<TreeNode> q=new LinkedList<>();
	q.add(root);
	while(!q.isEmpty()){
		TreeNode n=q.poll();
		System.out.print(n.val+" ");
		if(n.left!=null)
			q.add(n.left);
		if(n.right!=null)
			q.add(n.right);			
	}		
 }

分行打印

需记录每层的节点数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<List<Integer>> levelOrderBottom(TreeNode root) {
		List<List<Integer>> l=new ArrayList<>();		 
		if (root == null)
			return l;
		Queue<TreeNode> q = new LinkedList<>();
		q.add(root);
		while (!q.isEmpty()) {
			List<Integer> ll = new ArrayList<>();
			int size = q.size();//记录当前层的节点数
            while (size-- > 0) {
				TreeNode n = q.poll();
				ll.add(n.val);
				if (n.left != null) 
					q.add(n.left);				
				if (n.right != null)
					q.add(n.right);
			}
           // 从下往上遍历只需要把每一层得到的结果都方到list的头部！！
			l.add(0,ll);
		}
		return l;
    }

LeetCode的层次遍历