[数据结构与算法]leetcode 144

思路一：线索二叉树（Morris 遍历）

1.对于先序遍历而言，是先访问根节点，然后访问左子树、右子树。
2.记左子树根节点为L1，访问左子树过程中，也是按照根左右的方式，访问的最后一个节点必然是在L1的右子树L12，访问子树L12的最后一个节点也必然位于节点L12右子树当中，以此类推，访问以L1作为根的树过程中访问的最后一个节点就是沿着L1的右边子树的右子树的右子树的…右子树，直到右子树为叶子节点。
3.我们访问的顺序是根左右，在访问完左边子树后访问右子树需要重新返回根节点沿着其右孩子指针找到右子树，这个返回过程比较繁琐，需要在左子树中一层层回退，我们考虑是否能够在访问一个节点的同时提前将其左子树的最后访问的节点与当前节点连接起来，这样在访问完左子树之后就能够直接顺着链接就回退到当前节点然后访问当前节点的右子树。
4.由于左子树最后一个访问节点是叶子节点，所以其右孩子指针为空，我们可以将其指向当前根节点，这样能够节省空间。

实现：
1.记p1为当前访问根节点，p2指向当前根节点的左孩子。
2.如果p2非空，也就是左子树非空，那么便沿着p2的右孩子向右一直遍历，直到遍历到叶子节点，然后将叶子节点的右孩子指向p1，也就是当前根节点。
如果p2为空，则说明左子树为空，访问p1，让p1指向其右子树。返回1步骤
3.如果刚刚将将左子树的最后一个节点与根节点连接起来，则访问p1，让p1指向其左子树。返回步骤1
4.如果当前访问的是已经访问过的根节点，也就是左子树的最后一个节点与根节点连接起来了，则取消p2右孩子标记。转向步骤5
5.p1指向其右孩子。返回步骤1

代码：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        TreeNode* p1=root;
        TreeNode* p2;
        while(p1)
        {
            p2=p1->left;
            if(p2==NULL)
            {
                res.push_back(p1->val);
            }
            else
            {
                while(p2->right&&p2->right!=p1)
                    p2=p2->right;
                if(p2->right==NULL)
                {
                    res.push_back(p1->val);
                    p2->right=p1;
                    p1=p1->left;
                    continue;
                }
                else
                {
                    p2->right=NULL;
                }
            }
            p1=p1->right;
        }
        return res;
    }
};

思路二：栈辅助方式

1.根节点进栈。
2.如果栈非空，弹出栈顶元素作为当前访问子树的根节点，访问根节点。反之进入步骤4
3.如果右子树非空，则右孩子指针进入栈；如果左子树非空，则左孩子指针进入栈。转向步骤2
4.结束

代码：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        s.push(root);
        TreeNode *p=s.top();
        vector<int> res(100);
        int countt=0;
        while(p)
        {
            if(!s.empty())
                s.pop();
            if(p->right)
                s.push(p->right);
            if(p->left)
                s.push(p->left);
            res[countt++]=p->val;
            if(!s.empty())
                p=s.top();
            else
                p=NULL;
        }
        vector<int> new_res(res.begin(),res.begin()+countt);
        return new_res;
    }
};

思路三：递归

代码：

class Solution {
public:
    void First_order_trace(TreeNode* root,vector<int> &res)
    {
        if(!root)
            return;
        else
        {
            res.push_back(root->val);
            First_order_trace(root->left,res);
            First_order_trace(root->right,res);
        }
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        First_order_trace(root,res);
        return res;
    }
};