二叉樹前序Preorder周遊和後序Postorder周遊的非遞歸實作

1簡述

二叉樹的前序周遊和後序周遊的遞歸實作是相對容易實作的，而且非常便于了解。

對于前序周遊

       首先通路目前節點；

       如果左子樹非空，前序周遊左子樹；

       如果右子樹非空，前序周遊右子樹

對于後序周遊

       如果左子樹非空，後序周遊左子樹；

       如果右子樹非空，後序周遊右子樹；

       最後通路目前節點

2非遞歸實戰

當采用非遞歸方法來說實作時，就要略微複雜一些了。

       首先來看前序周遊

       根據前序周遊的定義，我們總是通路目前節點，通路左子樹，通路目前節點，通路左子樹。。。隻有當左子樹為空時才會去通路右子樹，接着就是重複這一過程；而當右子樹為空的時候，我們要退回到上一個節點，檢視上一個節點右子樹是否為空，若非空，接着重複通路過程。因為有一個後退的過程，是以我們考慮用棧來儲存通路經過的節點。在每次循環過程中，我們總會先判斷左子樹是否已經被通路過，是以我們需要對已經通路過的節點進行标記。對于LeetCode上的原題（網址https://oj.leetcode.com/problems/binary-tree-preorder-traversal/）來說，具體代碼過程如下：

public List<Integer> preorderTraversal(TreeNode root) {
		List<Integer> result = new LinkedList<Integer>(); // List to save the result of Binary Tree Preorder Traversal
		if(root == null) {
			return result;
		}
		
		Set<TreeNode> set = new HashSet<TreeNode>(); // Set to save the TreeNode that has been visited.
		Stack<TreeNode> stk = new Stack<TreeNode>(); // Stack to allow to step back to previous TreeNode
		TreeNode currentNode;
		
		// First, visit the root
		set.add(root);
		stk.push(root);
		result.add(root.val);

		while(!stk.isEmpty()) {
			currentNode = stk.peek(); // Get the top TreeNode that has been visited but not pop it.
			while(currentNode.left != null && !set.contains(currentNode.left)) { // Has left child but not been visited, just visit it!
				currentNode = currentNode.left;
				set.add(currentNode);
				stk.push(currentNode);
				result.add(currentNode.val);
			}
			// Visit until the left is null
			// Check whether has right child and if it is visited
			if(currentNode.right != null && !set.contains(currentNode.right)) {
				currentNode = currentNode.right;
				set.add(currentNode);
				stk.push(currentNode);
				result.add(currentNode.val);
			} else { // Has no right child, just pop it out
				stk.pop();
			}
		}
		return result;
	}
           

          後序周遊也來分析一下。後序周遊需要先周遊左子樹，再周遊右子樹，最後才是通路目前節點，和前序周遊一樣，也是需要棧的支援，儲存目前節點，然後左子樹非空通路左子樹，左子樹非空通路左子樹。。。直到左子樹為空，然後通路右子樹；在右子樹通路完了之後才通路該節點。對于LeetCode上的原題（網址https://oj.leetcode.com/problems/binary-tree-postorder-traversal/）來說，具體代碼如下：

public List<Integer> postorderTraversal(TreeNode root) {
		List<Integer> result = new ArrayList<Integer>();
		if(root == null) {
			return result;
		}
		
		Set<TreeNode> set = new HashSet<TreeNode>();
		Stack<TreeNode> stk = new Stack<TreeNode>();
		
		stk.push(root);
		TreeNode currentNode;
		
		while(!stk.isEmpty()) {
			currentNode = stk.peek(); // Get the top TreeNode but not pop it
			while(currentNode.left != null && !set.contains(currentNode.left)) { // Walk until left child is null, and check whether it has been visited
				stk.push(currentNode.left);
				currentNode = currentNode.left;
			}
			if(currentNode.right != null && !set.contains(currentNode.right)) { // push the right child if it has not been visited
				stk.push(currentNode.right);
			} else {                             // Has no right child or it has been visited before, just visit it!
				set.add(currentNode);
				result.add(currentNode.val);
				stk.pop();
			}
		}
		return result;
	}