專欄：Java數據結構秘籍

個人主頁：手握風云

目錄

一、非遞歸實現遍歷二叉樹

1.1.?二叉樹的前序遍歷

1.2.?二叉樹的中序遍歷

1.3.?二叉樹的后序遍歷

---

一、非遞歸實現遍歷二叉樹

1.1.?二叉樹的前序遍歷

????????我們這里要使用棧來進行實現。我們反向思考一下為什么不使用隊列？如下圖，前序遍歷肯定是先將根結點放進去，如果是隊列，根結點先進先出，然后怎么去遍歷右子樹呢，就無法打印的順序了。

????????我們定義一個引用cur，只要cur不為null，就打印值并將該元素放入棧中。當遍歷到4時，左子樹為空，返回結點4并彈出，再去遍歷4的右結點，然后返回結點2并彈出，讓cur等于結點2的右子樹并遍歷。只要1的左子樹沒有遍歷完，1就不彈出。

public class Solution {public void preorderTraversal(TreeNode root){if(root == null){return;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while(cur != null){stack.push(cur);System.out.print(cur.val+" ");cur = cur.left;}}
}

????????代碼寫到這里就會出現問題，原因是：當遍歷到結點4的時候，4的左子樹為空，就無法進入while循環。然后把4彈出去，讓cur=top，問題又來了，如果結點4左邊要是不為空，又得放入棧中，也需要走while循環。

????????我們會發現當cur走到某個結點時，如果為空，但棧不為空，此時就可以巧妙地在while外面再加一層while循環。

while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);System.out.print(cur.val + " ");cur = cur.left;}cur = stack.pop();cur = cur.right;
}

????????完整代碼實現：

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}public class Solution {public List<Integer> preorderTraversal(TreeNode root){List<Integer> tree = new ArrayList<>();if(root == null){return tree;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {while (cur != null) {tree.add(cur.val);stack.push(cur);cur = cur.left;}cur = stack.pop();cur = cur.right;}return tree;}
}

import java.util.ArrayList;
import java.util.List;public class Test {public static void main(String[] args) {List<Integer> result = new ArrayList<>();Solution solution = new Solution();TreeNode root = new TreeNode(1,new TreeNode(2),new TreeNode(3));root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);root.left.right.left = new TreeNode(6);root.left.right.right = new TreeNode(7);root.right.right = new TreeNode(8);root.right.right.left = new TreeNode(9);result = solution.preorderTraversal(root);System.out.println(result);}
}

1.2.?二叉樹的中序遍歷

????????與前序遍歷的思路相同，只是打印的時機不一樣。中序遍歷要在彈出的元素之后直接打印。

? ? ? ? 完整代碼實現：

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}public class Solution {public List<Integer> inorderTraversal(TreeNode root){List<Integer> tree = new ArrayList<>();if(root == null){return tree;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {while (cur != null) {tree.add(cur.val);stack.push(cur);cur = cur.left;}cur = stack.pop();tree.add(cur.val);cur = cur.right;}return tree;}
}

import java.util.ArrayList;
import java.util.List;public class Test {public static void main(String[] args) {List<Integer> result = new ArrayList<>();Solution solution = new Solution();TreeNode root = new TreeNode(1,new TreeNode(2),new TreeNode(3));root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);root.left.right.left = new TreeNode(6);root.left.right.right = new TreeNode(7);root.right.right = new TreeNode(8);root.right.right.left = new TreeNode(9);result = solution.inorderTraversal(root);System.out.println(result);}
}

1.3.?二叉樹的后序遍歷

? ? ? ? 后序遍歷不能按照我們上面前序與中序的方法來做。如果結點下面還有孩子結點，如果把4彈出之后，就無法獲取它的右側，所以只能獲取不能彈出。當右子樹為空，才能彈出，再進行打印。

public class Solution {public void postorderTraversal(TreeNode root){if(root == null){return;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode top = null;while(cur != null || !stack.isEmpty()) {while(cur != null){stack.push(cur);cur = cur.left;}top = stack.peek();if(top.right == null){stack.pop();System.out.print(top.val+" ");}else{cur = top.right;}}}
}public class Test {public static void main(String[] args) {Solution solution = new Solution();TreeNode root = new TreeNode(1,new TreeNode(2),new TreeNode(3));root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);root.left.right.right = new TreeNode(7);root.right.right = new TreeNode(8);root.right.right.left = new TreeNode(9);solution.postorderTraversal(root);}
}

????????但這樣寫，會存在問題：當遍歷到結點5的右結點7時，會陷入死循環。那我們怎么知道這個結點被打印過？我們再定義引用prev，讓prev來記錄被彈出的結點。

        while(cur != null || !stack.isEmpty()) {while(cur != null){stack.push(cur);cur = cur.left;}top = stack.peek();if(top.right == null || top.right == prev){stack.pop();System.out.print(top.val+" ");prev = top;}else{cur = top.right;}

????????完整代碼實現：

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}public class Solution {public List<Integer> postorderTraversal(TreeNode root){List<Integer> tree = new ArrayList<>();if(root == null){return tree;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode top = null;TreeNode prev = null;while(cur != null || !stack.isEmpty()) {while(cur != null){stack.push(cur);cur = cur.left;}top = stack.peek();if(top.right == null || top.right == prev){tree.add(top.val);stack.pop();prev = top;}else{cur = top.right;}}return tree;}
}

import java.util.ArrayList;
import java.util.List;public class Test {public static void main(String[] args) {List<Integer> tree = new ArrayList<>();Solution solution = new Solution();TreeNode root = new TreeNode(1,new TreeNode(2),new TreeNode(3));root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);root.left.right.left = new TreeNode(6);root.left.right.right = new TreeNode(7);root.right.right = new TreeNode(8);root.right.right.left = new TreeNode(9);tree = solution.postorderTraversal(root);System.out.println(tree);}
}