【算法】二叉樹、N叉樹先序、中序、後序、BFS、DFS周遊的遞歸和疊代實作記錄（Java版）

本文總結了刷LeetCode過程中，有關樹的周遊的相關代碼實作，包括了二叉樹、N叉樹先序、中序、後序、BFS、DFS周遊的遞歸和疊代實作記錄。

        本文總結了刷LeetCode過程中，有關樹的周遊的相關代碼實作，包括了二叉樹、N叉樹先序、中序、後序、BFS、DFS周遊的遞歸和疊代實作。這也是解決樹的周遊問題的固定套路。

一、二叉樹的先序、中序、後序周遊

  1、遞歸模闆

  （1）先序

1 public void preorder(TreeNode root) {
2    if (root == null) {
3        return;
4    }
5    res.add(root.val);
6    preorder(root.left);
7    preorder(root.right);
8 }      

  （2）中序

1 public void inorder(TreeNode root) {
2    if (root == null) {
3       return;
4    }
5    inorder(root.left);
6    res.add(root.val);
7    inorder(root.right);
8 }      

  （3）後序

1 public void postorder(TreeNode root) {
2     if (root == null) {
3        return;
4     }
5     postorder(root.left);
6     postorder(root.right);
7     res.add(root.val);
8 }      

  2、疊代模闆:顯式使用棧

  （1）先序 。也可以使用後文的DFS實作

1 public void preorder(TreeNode root) {
 2      Deque<TreeNode> stack = new ArrayDeque<>();
 3       while(root !=null || !stack.isEmpty()) {
 4          while(root != null) {
 5             stack.push(root);
 6             res.add(root.val);//儲存結果
 7             root = root.left;
 8          }
 9          root = stack.pop();
10          root = root.right;
11       }
12 }      

1 public void inorder(TreeNode root) {
 2     Deque<TreeNode> stack = new ArrayDeque<>();
 3     while(root != null || !stack.isEmpty()) {
 4        while(root != null) {
 5           stack.push(root);
 6           root = root.left;
 7        }
 8        root = stack.pop();
 9        res.add(root.val);//儲存結果
10        root = root.right;
11     }
12 }      

  （3）後序。先序是根——左——右，而後序是左-右-根，可以将先序改成根-右-左，然後将結果反轉。如下代碼對比先序的代碼：

1 public void postorder(TreeNode root) {
 2     Deque<TreeNode> stack = new ArrayDeque<>();
 3      while(root != null || !stack.isEmpty()) {
 4          while(root != null) {
 5             stack.push(root);
 6             res.add(root.val);//儲存結果
 7             root = root.right;//注意這裡和先序、中序的差别
 8          }
 9          root = stack.pop();
10          root = root.left();
11      }
12      Collections.reverse(res);//将前面的結果反轉
13 }      

       當然，上面這種方法比較間接，借助于先序周遊的了解。下面采用一種直接的疊代方式：

1 public void postorder(TreeNode root) {
 2     Deque<TreeNode> stack = new ArrayDeque<>();
 3     TreeNode preNode = new TreeNode();//該節點用于儲存前一個出棧的節點
 4     while (root != null || !stack.isEmpty()) {
 5         //将目前節點的左子樹節點一次入棧
 6         while (root != null) {
 7             stack.push(root);
 8             root = root.left;
 9         }
10         root = stack.peek();
11         //目前節點沒有右孩子了，或者其右孩子已經出棧了，則目前節點也出棧
12         if (root.right == null || root.right == preNode) {
13             root = stack.pop();
14             res.add(root.val);//儲存結果
15             preNode = root; //記錄本次剛輸出的節點
16             root = null;
17         } else {
18             //目前節點還有右孩子，且其右孩子還沒有出棧，則先處理其右孩子
19             root = root.right;
20         }
21     }
22 }      

二、N叉樹的先序與後序周遊

1 public void preorder(TreeNode root) {
 2     if (root == null) {
 3         return;
 4     }
 5     res.add(root.val);//儲存結果
 6     if (root.children != null) {
 7         for (int i = 0; i < root.children.size(); i++) {
 8             dfs(root.children.get(i));
 9         }
10     }
11 }      

  （2）後序

1 public void postorder(TreeNode root) {
2     if (root == null) {
3         return;
4     }
5     for (int i = 0; i < root.children.size(); i++) {
6         postorder(root.children.get(i));
7     }
8     res.add(root.val);//儲存結果
9 }      

  2、疊代模闆

  （1）先序。即下文中DFS的實作

1 public void preorder(Node root) {
 2    Deque<Node> stack = new ArrayDeque<>(); //BFS使用隊列，這裡使用棧
 3    stack.push(root);
 4    while (!stack.isEmpty()) {
 5        root = stack.pop();
 6        res.add(root.val);//儲存結果
 7        int childCount = root.children == null ? 0 : root.children.size();
 8        //這裡需要注意孩子節點入棧的順序
 9         for (int i = childCount - 1; i >= 0; i--) {
10            stack.push(root.children.get(i));
11        }
12    }
13 }      

  （2）後序。先序是根——左——右，而後序是左-右-根，可以将先序改成根-右-左，然後将結果反轉。如下代碼對比先序的代碼：

1 public void postorder(Node root) {
 2    List<Integer> result = new ArrayList<>();
 3    Deque<Node> stack = new ArrayDeque<>();
 4    stack.push(root);
 5    while (!stack.isEmpty()) {
 6        root = stack.pop();
 7        result.add(root.val);//儲存結果
 8        int childCount = root.children == null ? 0 : root.children.size();
 9         //還入棧的順序正好和先序周遊相反
10        for (int i = 0; i < childCount; i++) {
11            stack.push(root.children.get(i));
12        }
13    }
14     //将結果反轉
15    Collections.reverse(result);
16    for (Integer i:result) {
17        System.out.print(i);
18    }
19 }      

       目前還沒有找到類似二叉樹直接後序周遊的方法

三、樹的BFS(廣度優先搜尋)和DFS(深度優先搜尋)實作模闆

  1、遞歸實作

  （1）BFS

          一般來說不能使用遞歸來實作BFS，因為BFS使用的時隊列實作，而遞歸使用的是棧實作。

  （2）DFS

          普通的N叉樹的DFS包括先序周遊和後序周遊，它們的遞歸實作和前文一緻。如果是二叉樹，還有中序周遊，遞歸實作和前文一緻。

  2、疊代實作

  （1）BFS。即按層次來周遊

1 public void bfs(Node root) {
 2    Queue<Node> queue = new LinkedList<>();
 3    queue.offer(root);
 4    while (!queue.isEmpty()) {
 5        root = queue.poll();
 6        res.add(root.val);//儲存結果
 7        if (root.children != null) {
 8            queue.addAll(root.children);//這裡的addAll後，root的children會從左往右依次入隊。這一點Deque實作的棧正好相反，這一點需要注意
 9        }
10    }
11 }      

  （2）DFS

       先序周遊、中序周遊(二叉樹)和後序周遊的疊代方式實作和前文一緻。

四、圖的BFS和DFS周遊模闆

        樹是圖的一種特殊情況，相比于樹而言圖中可能出現環，是以在周遊的時候可能重複通路。是以樹的BFS和DFS實作需要在樹的基礎上維護一個Set來避免通路重複的節點即可。

  1、BFS

1 public void graphyBfs(Node root) {
 2     if (root == null) {
 3         return;
 4     }
 5     Set<Node> visitedSet = new HashSet<>(); //維護一個set，儲存已經通路過的節點
 6     Queue<Node> queue = new LinkedList<>();
 7     queue.offer(root);
 8     while (!queue.isEmpty()) {
 9         root = queue.poll();
10         visitedSet.add(root);//儲存每個已經輸出的節點
11         res.add(root.val);//儲存結果
12         if (root.children == null) {
13             return;
14         }
15         for (int i = 0; i < root.children.size(); i++) {
16             Node tmpNode = root.children.get(i);
17             if (!visitedSet.contains(tmpNode)) {//已經輸出過的節點，則不用再加入
18                 queue.offer(tmpNode);
19             }
20         }
21     }
22 }      

  2、DFS

       疊代方式、遞歸方式，都維護一個set來儲存已經通路過的節點，在輸出節點時儲存到set中，在添加節點時添加去重操作即可。