739
LeetCode題目詳解——Binary Tree Preorder Traversal
題目：
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?
二叉樹的遍曆是一個基礎問題，具體涉及到先序、中序和後序問題，基本的方法有遞歸和非遞歸，其中非遞歸的思路又分為使用棧以及不使用棧。遞歸的方法代碼很簡單，但是開銷很大，所以在此不表。僅針對leetcode上對應的題目給出非遞歸的兩種方法。
一、使用棧
二叉樹非遞歸遍曆很自然地會聯想到使用棧來記錄還沒有訪問的節點。每次從棧中pop出一個節點，並訪問該節點，同時將其右左子樹（順序很重要，是右左）壓入棧中，直到棧為空的時候，遍曆結束。代碼如下：
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
stack<TreeNode*> nodeStack;
vector<int> valVec;
if(!root)
return valVec;
nodeStack.push(root);
while(!nodeStack.empty())
{
TreeNode* top = nodeStack.top();
valVec.push_back(top->val);
nodeStack.pop();
if(top->right)
nodeStack.push(top->right);
if(top->left)
nodeStack.push(top->left);
}
}
};
二、不使用棧
使用棧的作用就是利用棧來記錄接下來需要訪問的節點，如果不使用棧的話，那麼就必須想出其他的方法來記錄接下來需要訪問的節點。Morris設計出利用改變樹本身的結構來記錄接下來需要訪問的節點，並在訪問完之後再將樹的節點改變回來。具體的思路就是：對於當前要訪問的節點curNode，找到左子樹的最右節點tmp（如果沒有左子樹就不必了），然後將curNode節點賦值給tmp的右子樹。這樣就可以利用樹本身的結構來記錄需要訪問的信息。當訪問完curNode的左子樹之後，再將tmp的右子樹賦值為NULL，以恢複樹原有的結構。代碼如下：
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
vector<int> valVec;
TreeNode *p=root;
if(!root)
return valVec;
while(p)
{
if(p->left==NULL)
{
valVec.push_back(p->val);
p=p->right;
}
else
{
TreeNode *tmp=p->left;
while(tmp->right && tmp->right !=p)
{
tmp=tmp->right;
}
if(tmp->right==NULL)
{
valVec.push_back(p->val);
tmp->right=p;
p=p->left;
}
else
{
tmp->right=NULL;
p=p->right;
}
}
}
}
};
如果覺得還是不好理解的話，那麼可以看看接下來的幾幅圖以幫助理解。
最後更新：2017-04-03 05:39:56