二叉樹遍歷與剪枝

來自專欄演算法學習

目前工作中遇到如下問題，對象之間有依賴關係，抽象來看作一棵二叉樹，最上層的是root節點，而父節點會依賴子節點。如果現在有一些節點已經標記為無效，我們要刪除這些無效節點。如果無效節點的依賴的節點還有效，那麼不應該刪除，如果無效節點和它的子節點都無效，則可以刪除。

如下圖所示

看到這個問題，第一個想法就是遞歸，而二叉樹的遞歸有:前序遍歷，中序遍歷和後序遍歷。

最開始我只是確定要遞歸，根本就沒有考慮什麼順序，我的流程如下：

public TreeNode pruneTree (TreeNode root) {if (root.val ==0 && root.left.val == 0 && root.right.val ==0) { return null;} root.left= pruneTree(root.left); root.right= pruneTree(root.right);}

這裡看到一個明顯的異常的情況是

因此剪枝只能從葉子節點開始遍歷，然後再遍歷父節點，這樣才能保證每次剪枝是逐級剪去無用的節點，到父節點的時候無用的節點都已經去掉，只需要判斷當前節點和它的子節點是否為0就可以了。這個時候我明白，和二叉樹的遍歷順序有關係。

在遞歸裡面前序，中序和後序代表的遍歷順序和處理邏輯的順序如下：

前序遍歷

public TreeNode pruneTree (TreeNode root) { //前序 doSomeThing();root.left =pruneTree(root.left); root.right= pruneTree(root.right);}

中序遍歷

public TreeNode pruneTree (TreeNode root) {root.left =pruneTree(root.left); //中序 doSomeThing(); root.right= pruneTree(root.right);}

後續遍歷

public TreeNode pruneTree (TreeNode root) {root.left =pruneTree(root.left); root.right= pruneTree(root.right);//後續 doSomeThing();}

上面遞歸中不通的順序就代表了不同的遍歷順序，同時代表了不同的實現，在二叉樹遍歷過程中要注意不同遍歷順序的要求。

推薦閱讀：