Preorder:

因為是preorder traversal, 我們需要先print root，然后左節點，最后右節點，而且root左邊子樹一定比右邊子樹先print出來，所以，我們可以先把當前root的右節點壓棧，然后把root的左節點壓棧，這樣每次從棧里取的時候，可以保證左邊節點的root先取。同時，每次取了當前節點，我們進行同樣的操作（先壓右節點，再壓左節點），這樣可以保證preorder traversal。

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/ class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if (root == null) return list;Stack<TreeNode> s = new Stack<TreeNode>();s.push(root);while (!s.empty()) {TreeNode node = s.pop();list.add(node.val);if (node.right != null) {s.push(node.right);}if (node.left != null) {s.push(node.left);}}return list;} }

Inorder:

因為inorder 需要先打印最左邊，然后root，然后最右邊，所以，我們一定要先reach到樹的最左邊，直到沒有左子樹為止，并同時把root加入到stack里。

當當前node沒有左子樹，表面我們已經到達樹的最左邊，我們需要把stack最上面的root打出來，然后當前root指向root.right. 然后把右子樹當成一顆樹使用同樣的遍歷即可。這題的關鍵點之一是那個while條件，也就是說，只要stack不為空或者當前node不是null, 我們就應該繼續。

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();while(!stack.isEmpty() || root != null) {if (root != null) {stack.push(root);root = root.left;} else {root = stack.pop();list.add(root.val);root = root.right;}}return list;} }

?

Postorder:

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new LinkedList<>();if (root == null) return list;Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()) {root = stack.pop();list.add(0, root.val);if (root.left != null) { stack.push(root.left); }if (root.right != null) { stack.push(root.right); }}return list;} }

?

轉載于:https://www.cnblogs.com/beiyeqingteng/p/5743214.html

總結

以上是生活随笔為你收集整理的Binary Tree Non-recursive Traversal的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。