[LeetCode] 144. Binary Tree Preorder Traversal

轉自LeetCode

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

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

   1
    \
     2
    /
   3

return [1,2,3].

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

<Solution>

題目有要求要用 iterative 的做法，不要用 recursive

那這時候就多用一個 stack 來幫忙

• 第一個當然是把 root 丟進去 stack

• stack 不為空，就一直迴圈

• 拿 top 出來，將其值放到 ans 裡

• 先檢查 right child，有 right child 就放到 stack

• 再檢查 left child，有 left child 就放到 stack

Note: 因為 stack 是 LIFO，且 preorder traversal 的順序是 root->left->right，所以先看right再看left

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> preorderTraversal(TreeNode* root) {
	vector<int> ans;
	if(!root) {
	return ans;
	}
	stack<TreeNode *> treeStack;
	//> initial
	treeStack.push(root);
	while(!treeStack.empty()) {
	TreeNode *tmpN = treeStack.top();
	treeStack.pop();
	ans.push_back(tmpN->val);
	if(tmpN->right) {
	treeStack.push(tmpN->right);
	}
	if(tmpN->left) {
	treeStack.push(tmpN->left);
	}
	}
	return ans;
	}
	};

view raw preorderTraversal_1.cpp hosted with ❤ by GitHub

這邊也可以用 morris traversal 來做 preorder traversal

和 inorder traversal 不同的地方只在於輸出順序

因為 inorder 是 left->root->right，preorder 是 root->left->right

所以不用等 left node 都結束再印出 root，而是要先印出來

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> preorderTraversal(TreeNode* root) {
	vector<int> ans;
	if(!root) {
	return ans;
	}
	TreeNode *curr = root, *prev = NULL;
	//> preorder traversal
	while(curr) {
	if(!curr->left) {
	//> leftest leaf node
	ans.push_back(curr->val);
	curr = curr->right;
	}
	else {
	//> find predecessor
	prev = curr->left;
	while(prev->right && prev->right != curr) {
	prev = prev->right;
	}
	if(!prev->right) {
	//> preoreder traversal : root->left->right
	//> the only difference between inorder Morris traversal
	ans.push_back(curr->val);
	//> transform to threaded tree
	prev->right = curr;
	//> keep going left
	curr = curr->left;
	}
	else {
	//> all left nodes of curr are done
	//> change threaded tree back to binary tree
	prev->right = NULL;
	//> make right node as new root
	curr = curr->right;
	}
	}
	}
	return ans;
	}
	};

view raw preorderTraversal_2.cpp hosted with ❤ by GitHub