快捷導(dǎo)航

Java 二叉樹遍歷的常用方法

更新時間：2021年05月28日 09:15:41 作者：vcjmhg

二叉樹的遍歷可以說是解決二叉樹問題的基礎(chǔ)。我們常用的遍歷方式無外乎就四種前序遍歷、中序遍歷、后續(xù)遍歷、層次遍歷這四種。

采用前序遍歷、中序遍歷、后續(xù)遍歷實現(xiàn)時，即便采用不同的實現(xiàn)方式（遞歸方式、非遞歸），它們的算法結(jié)構(gòu)是有很大的相似性。因而針對前三種的遍歷我們會總結(jié)出對應(yīng)通用的解決框架，便于在解決二叉樹問題時進(jìn)行使用。

遞歸方式

遞歸方式遍歷二叉樹時，無論是前序遍歷、中序遍歷還是后續(xù)遍歷的方式，它們最大的區(qū)別就是對節(jié)點數(shù)據(jù)的訪問位置不同。除此之外其結(jié)構(gòu)完全一致，因而我們總結(jié)出如下的框架結(jié)構(gòu)：

void traverse(TreeNode root) {
    //終止條件
    if(root == null) return;
    // 前序遍歷
    traverse(root.left);
    // 中序遍歷
    traverse(root.right);
    // 后序遍歷
}

對應(yīng)注釋的位置訪問數(shù)據(jù)就可以實現(xiàn)不同的遍歷方式。

例如，前序遍歷：

void traverse(TreeNode root) {
    if(root == null) return;
    visit(root);
    traverse(root.left);
    traverse(root.right);
}

同樣的中序遍歷：

void traverse(TreeNode root) {
    if(root ==null) return;
    traverse(root.left);
    visit(root);
    traverse(root.right);
}

后續(xù)遍歷：

void traverse(TreeNode root) {
    if(root ==null) return;
    traverse(root.left);
    traverse(root.right)
}

是否非常 easy??！

非遞歸方式

二叉樹非遞歸遍歷說實話有很多種實現(xiàn)方式，但本質(zhì)上都是模擬整個遍歷的過程來實現(xiàn)的。

為了便于理解，其中前序遍歷、中序遍歷、后序遍歷我們采用一套類似的算法框架。

整個算法框架如下：

 public void traverse(TreeNode root) {
    // 邊界判斷
    if (root == null) {
      return;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    while (current != null || !stack.isEmpty()) {
       //節(jié)點非空時，證明父節(jié)點的左側(cè)節(jié)點非空，直接入棧
      if (current != null) {
        //前序遍歷 visit(current)
        stack.push(current);
        current = current.left;
      } else {
        //節(jié)點為空，證明左側(cè)節(jié)點為空，出棧，更換游標(biāo)節(jié)點方向
        current = stack.pop();
		//中續(xù)遍歷 visit(current);
        current = current.right;
      }
    }
  }

后序遍歷它的遍歷順序為**"左--> 右--> 根"，較之與前序遍歷的"根--> 左--> 右"，好像是有很大的相似性，我們能否針對上邊的框架進(jìn)行修改，使由前序遍歷轉(zhuǎn)換成后序遍歷？？
答案是肯定的，我們可以觀察到，可以先求出遍歷順序是"根--> 右--> 左"**"的節(jié)點序列，再倒序，便剛好是后序遍歷的順序：左右根。而遍歷順序是根右左的話，很好辦，從前序遍歷的代碼中改兩行就是了。

故而，可以選擇使用兩個棧，其中一個用于遍歷，另一個用于結(jié)果的倒序。

實現(xiàn)代碼如下：

//使用雙棧來實現(xiàn)后序遍歷
  public void postOrderTraverse(TreeNode root){
    Stack<TreeNode> stack = new Stack<>();
    Stack<Integer> res = new Stack<>();
    TreeNode cur = root;
    while (cur!=null || !stack.isEmpty()) {
      if (cur!=null){
        stack.push(cur);
        res.push(cur.val);
        cur = cur.right; //修改處
      }else{
        cur = stack.pop();
        cur = cur.left;  // 修改處
      }
    }
    while (!res.isEmpty()){
      visit(res.pop());
    }
  }

至此，非遞歸遍歷完成，是不是也很 easy??！

下邊我們可以看一下最后一種層次遍歷

層次遍歷

層次遍歷本質(zhì)上就是閹割版廣度優(yōu)先遍歷，我們此處就直接給出 BFS 算法的框架：

/**
* 給定起始節(jié)點start和目標(biāo)節(jié)點target，返回其最短路徑長度
**/
int BFS(Node start,Node target){
    Queue<Node> q; //核心數(shù)據(jù)結(jié)構(gòu)
    Set<Node> visited: //某些情況下可以通過byte數(shù)組來進(jìn)行代替
    int step = 0; //記錄擴(kuò)散步數(shù)
    //起始節(jié)點入隊列
    q.add(start);
    visited.offer(start);
    while(q not empty) {
        //必須要用sz來保存q.size()，然后擴(kuò)散sz不能直接使用q.size()
        int sz = q.size();
        //將隊列中的節(jié)點進(jìn)行擴(kuò)散
        for(int i =0 ; i < sz; i++) {
            Node cur = q.poll();
            // 目標(biāo)節(jié)點判斷
            if(cur is target) {
                return step;
            }
            // 鄰接結(jié)點入隊列
            for(Node n:cur.adjs) {
                //未訪問節(jié)點入隊列
                if(n is not int visited) {
                    visitd.add(n);
                    q.offer(n);
                }
            }
        }
        // 更新步數(shù)
        step++;
    }
}

此處我們借助 BFS 的框架，直接給出其實現(xiàn)方法：

void LevelOrder(TreeNode root){
    //初始化棧，并放入
    Queue<TreeNode> queue;
    queue.add(root);
    while( !queue.isEmpty()) {
        //出棧
        TreeNode cur = queue.poll();
        //訪問節(jié)點
        visit(cur);
        //向下一層級擴(kuò)散
        if(cur.left !=null) queue.add(cur.left);
        if(cur.right !=null) queue.add(cur.right);
    }
}

較之于 BFS，我們會發(fā)現(xiàn)，層次遍歷，少了好多東西，比如不需要 visited 來標(biāo)記已訪問的節(jié)點（二叉樹本身結(jié)構(gòu)的特點，不可能出現(xiàn)重復(fù)遍歷），也不需要將隊列中的節(jié)點進(jìn)行擴(kuò)散等。