二叉樹的遍歷方式包括前序遍歷、中序遍歷和后序遍歷，其實作方式包括遞回實作和非遞回實作，
前序遍歷：根節點 | 左子樹 | 右子樹
中序遍歷：左子樹 | 根節點 | 右子樹
后序遍歷：左子樹 | 右子樹 | 根節點
1. 遞回實作
遞回方式實作代碼十分簡潔，三種遍歷方式的遞回實作代碼結構相同，只是執行順序有所區別，
前序遍歷：
public class preOrderRecur {
List<Integer> res = new ArrayList<>();
public List<Integer> preOrderTraversal(TreeNode root) {
if (root != null) {
res.add(root.val); // 根節點
preOrderTraversal(root.left); // 左子樹
preOrderTraversal(root.right); // 右子樹
}
return res;
}
}
中序遍歷：
public class inOrderRecur {
List<Integer> res = new ArrayList<>();
public List<Integer> inOrderTraversal(TreeNode root) {
if (root != null) {
inOrderTraversal(root.left); // 左子樹
res.add(root.val); // 根節點
inOrderTraversal(root.right); // 右子樹
}
}
return res;
}
后序遍歷：
public class inOrderRecur {
List<Integer> res = new ArrayList<>();
public List<Integer> inOrderTraversal(TreeNode root) {
if (root != null) {
inOrderTraversal(root.left); // 左子樹
inOrderTraversal(root.right); // 右子樹
res.add(root.val); // 根節點
}
}
return res;
}
2. 迭代實作
2.1 使用輔助堆疊——空間復雜度O(N)
2.1.1 中序遍歷
- 從當前結點一直向其最左孩子搜索，直到沒有左孩子了停止，這個程序中將路程中的所有結點入堆疊；
- 彈出堆疊頂元素，將其記錄在答案中，并把當前結點置為彈出元素的右孩子并重復第一步程序，
public class inOrderIterator {
List<Integer> res = new ArrayList<>();
public List<Integer> inOrderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
if (root != null) {
stack.push(root);
root = root.left;
} else {
TreeNode node = stack.pop();
res.add(node.val);
root = node.right;
}
}
return res;
}
}
2.1.2 前序遍歷
方法1：因為前序遍歷訪問順序是“中-左-右”，所以可以先將根結點壓堆疊，然后按照下列步驟執行，
- 如果堆疊不為空，則彈出堆疊頂元素存入結果中；
- 如果彈出元素的右孩子不為空則將右孩子壓堆疊，然后如果其左孩子也不為空將其左孩子壓堆疊（因為堆疊是后入先出的，所以為了達到“中-左-右”的順序，需要先壓入右孩子，再壓入左孩子），
public class preOrderIterator {
List<Integer> res = new ArrayList<>();
public List<Integer> inOrderTraversal(TreeNode root) {
if (root == null) return res;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
root = stack.pop();
res.add(root.val);
// 右孩子壓堆疊
if (root.right != null) stack.push(root.right);
// 左孩子壓堆疊
if (root.left != null) stack.push(root.left);
}
return res;
}
}
方法2：根據中序遍歷進行微調：
public class preOrderIterator {
List<Integer> res = new ArrayList<>();
public List<Integer> inOrderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
if (root != null) {
res.add(root.val);
stack.push(root);
root = root.left;
} else {
TreeNode node = stack.pop();
root = node.right;
}
}
return res;
}
}
2.1.3 后序遍歷
因為前序遍歷的順序是“左-中-右”，而后序遍歷順序是“左-右-中”，不考慮左結點，區別只是在于中結點和右結點的順序進行了反向而已，因此可以使用前序遍歷的代碼進行調整，只需要將前序遍歷對左右孩子壓堆疊的順序反向即可，即先壓入左孩子，再壓入右孩子，除此之外，因為按照這種方法調整得到的遍歷順序為“中-右-左”，正好是后序遍歷的反向順序，因此在獲得遍歷序列后還需進行逆序操作，
public class postOrderIterator {
List<Integer> res = new LinkedList<>();
public List<Integer> postOrderTraversal(TreeNode root) {
if (root == null) return res;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
root = stack.pop();
// 頭插法
res.add(0, root.val);
// 左孩子壓堆疊
if (root.left != null) stack.push(root.left);
// 右孩子壓堆疊
if (root.right != null) stack.push(root.right);
}
return res;
}
}
2.2 Morris遍歷——空間復雜度O(1)
該方法的思路簡單說就是，對于每一個結點，找到它左孩子的最右子結點，因為按照正常訪問順序，其左孩子的最有子節點訪問完后就應該訪問其本身了，因此將其左孩子最右子節點的右指標指向它，基本步驟如下：
- 如果當前結點左孩子為空，說明最左邊訪問完畢，將其置為其右孩子
- 如果當前結點左孩子不為空，那么開始嘗試找到該結點左孩子的最右子節點，建立連接關系
- 如果找到的當前結點的左孩子的最右子節點右指標為空，說明還未建立連接關系，是首次訪問當前結點，那么將該最右結點的右指標指向當前結點，然后當前結點向左孩子走一步繼續重復所有步驟，
- 如果找到的當前結點的左孩子的最右子節點右指標不為空，說明已建立過連接關系，是第二次訪問當前結點，這意味著當前結點的左子樹應該已經全部遍歷完了，此時應恢復連接關系重新置為空，然后當前結點向右孩子走一步繼續重復所有步驟，
該方法雖然保證了O(1)的空間復雜度，但在遍歷程序中改變了部分結點的指向，破壞了樹的結構，
2.2.1 中序遍歷
public class inOrderMorris {
List<Integer> res = new ArrayList<>();
public List<Integer> inOrderTraversal(TreeNode root) {
TreeNode pre = null;
TreeNode cur = root;
while (cur != null) {
if (cur.left == null) {
res.add(cur.val);
cur = cur.right;
} else {
pre = cur.left;
while (pre.right != null && pre.right != cur) pre = pre.right;
if (pre.right == null) {
pre.right = cur;
cur = cur.left;
} else {
res.add(cur.val);
pre.right = null;
cur = cur.right;
}
}
}
return res;
}
}
2.2.2 前序遍歷
public class preOrderMorris {
List<Integer> res = new ArrayList<>();
public List<Integer> preOrderTraversal(TreeNode root) {
TreeNode pre = null;
TreeNode cur = root;
while (cur != null) {
if (cur.left == null) {
res.add(cur.val);
cur = cur.right;
} else {
pre = cur.left;
while (pre.right != null && pre.right != cur) pre = pre.right;
if (pre.right == null) {
res.add(cur.val);
pre.right = cur;
cur = cur.left;
} else {
pre.right = null;
cur = cur.right;
}
}
}
return res;
}
}
2.2.3 后序遍歷
前序遍歷反向的思想
public class postOrderMorris {
List<Integer> res = new LinkedList<>();
public List<Integer> postOrderTraversal(TreeNode root) {
TreeNode pre = null;
TreeNode cur = root;
while (cur != null) {
if (cur.right == null) {
res.add(0, cur.val);
cur = cur.left;
} else {
pre = cur.right;
while (pre.left != null && pre.left != cur) pre = pre.left;
if (pre.left == null) {
res.add(0, cur.val);
pre.left = cur;
cur = cur.right;
} else {
pre.left = null;
cur = cur.left;
}
}
}
return res;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/59825.html
標籤：Java
上一篇：還不會使用Java ThreadLocal落后了吧！
下一篇：Java成員變數和區域變數的區別