[LeetCode] 94. Binary Tree Inorder Traversal

轉自LeetCode

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

For example:
Given binary tree [1,null,2,3],

   1
    \
     2
    /
   3

return [1,3,2].

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

<Solution>

這題是要做 inorder 的 traversal，一樣只使用 iterative 的方式

還是多用一個 stack 來幫忙，按照 inorder traversal 的方式塞到 stack 就好

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> inorderTraversal(TreeNode* root) {
	vector<int> ans;
	stack<TreeNode *> nodeStack;
	//>> inorder traversal
	while(root || !nodeStack.empty()) {
	//>> find left most node
	while(root) {
	nodeStack.push(root);
	root = root->left;
	}
	//>> output value of left most node
	root = nodeStack.top();
	nodeStack.pop();
	ans.push_back(root->val);
	//>> make right child as new root
	root = root->right;
	}
	return ans;
	}
	};

view raw inorderTraveersal_1.cpp hosted with ❤ by GitHub

這邊再多看一個時間複雜度O(n)，空間複雜度為 O(1) 的 inorder traversal 方式

意即不用再多一個 stack 的方式

叫做 Morris Traversal，這種方式會用到一個資料結構叫 threaded tree

想法如下

• curr 一開始指向 root

• curr 不是 NULL 的話，重複以下步驟

• 如果 curr 沒有左節點

• 輸出 curr->val

• curr 指向右節點

• 如果 curr 有左節點

• 在左子樹裡面找到最右節點

• 如果最右節點的 right = NULL，將 right = curr，代表 curr 是最右節點的 predecessor(此右節點結束後，回到 curr)

• 如果最右節點 right != NULL，代表 curr 的所有左節點都完成的，按照 inorder 的順序(left -> root -> right)，此時就是輸出 curr->val，然後把 curr = curr->right

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> inorderTraversal(TreeNode* root) {
	vector<int> ans;
	if(!root) {
	return ans;
	}
	TreeNode *curr = root, *prev = NULL;
	//> inorder traversal
	while(curr) {
	if(!curr->left) {
	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) {
	//> transform binary tree to threaded tree
	prev->right = curr;
	curr = curr->left;
	}
	else {
	//> all left nodes of curr are done
	//> output curr itself
	ans.push_back(curr->val);
	//> change threaded tree back to binary tree
	prev->right = NULL;
	//> make right node as new root
	curr = curr->right;
	}
	}
	}
	return ans;
	}
	};

view raw inorderTraveersal_2.cpp hosted with ❤ by GitHub