[LeetCode] 145. Binary Tree Postorder Traversal

轉自LeetCode

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

<Solution>

binary tree traversal 相關問題，這次是要用 postorder : left -> right -> root

一樣使用 iterative 的方式

想法上和 preoder 差不多，但是因為 root 放到最後面去

所以要多一個 node 來記錄某 node 的 child 是否都被訪問過了

code 如下

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	vector<int> postorderTraversal(TreeNode* root) {
	vector<int> ans;
	if(!root) {
	return ans;
	}
	TreeNode *latestPopNode = root;
	stack<TreeNode *> treeStack;
	treeStack.push(root);
	//> postorder traversal
	while(!treeStack.empty()) {
	TreeNode *tmpN = treeStack.top();
	//> leaf node or child nodes are all done
	if((!tmpN->left && !tmpN->right) || tmpN->left == latestPopNode || tmpN->right == latestPopNode) {
	ans.push_back(tmpN->val);
	treeStack.pop();
	latestPopNode = tmpN;
	}
	else {
	if(tmpN->right) {
	treeStack.push(tmpN->right);
	}
	if(tmpN->left) {
	treeStack.push(tmpN->left);
	}
	}
	}
	return ans;
	}
	};

view raw postorderTraversal_1.cpp hosted with ❤ by GitHub

那當然也可以使用 Morris Traversal，來將空間使用度變成O(1)

但必須修正一下原本的 morris traversal

• 多用一個 dummy head，並把原本的 tree 放到左邊

• output 的地方，改成統一在 left nodes 都跑完後，用 reverse 的方式，將 node 印出來

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	vector<int> postorderTraversal(TreeNode* root) {
	vector<int> ans;
	if(!root) {
	return ans;
	}
	//> use a dummy head
	TreeNode *dummy = new TreeNode(0);
	dummy->left = root;
	TreeNode *curr = dummy, *prev = NULL;
	//> use same logic as inorder traversal
	//> but deal output with reverse logic
	while(curr) {
	if(!curr->left) {
	//> simply go to right node
	curr = curr->right;
	}
	else {
	//> find predecessor
	prev = curr->left;
	while(prev->right && prev->right != curr) {
	prev = prev->right;
	}
	if(!prev->right) {
	//> transform to threaded tree
	prev->right = curr;
	//> keep going left
	curr = curr->left;
	}
	else {
	//> output val in reverse order
	outputReverse(curr->left, prev, ans);
	//> change threaded tree back to binary tree
	prev->right = NULL;
	//> make right node as new root
	curr = curr->right;
	}
	}
	}
	return ans;
	}
	void outputReverse(TreeNode *from, TreeNode *to, vector<int> &ans) {
	reverseTree(from, to);
	TreeNode *curr = to;
	while(true) {
	ans.push_back(curr->val);
	if(curr == from) {
	break;
	}
	curr = curr->right;
	}
	reverseTree(to, from);
	}
	void reverseTree(TreeNode *from, TreeNode *to) {
	if(from == to) {
	return;
	}
	TreeNode *a = from, *b = from->right, *c;
	while(true) {
	c = b->right;
	b->right = a;
	a = b;
	b = c;
	if(a == to) {
	break;
	}
	}
	}
	};

view raw postorderTraversal_2.cpp hosted with ❤ by GitHub