144. Binary Tree Preorder Traversal.md

144. 二叉树的前序遍历

给定一个二叉树，返回它的 前序 遍历。

 示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解法一：

//时间复杂度O(n), 空间复杂度O(n)
/**
 * 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) {
        if(!root) return {};
        stack<TreeNode*> st;
        st.push(root);
        vector<int> vec;
        while(!st.empty()) {
            TreeNode* temp = st.top();
            st.pop();
            vec.push_back(temp->val);
            if(temp->right) st.push(temp->right);
            if(temp->left) st.push(temp->left);
        }
        return vec;
    }
};

解法二：

//时间复杂度O(n), 空间复杂度O(1)
/**
 * 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> vec;
        TreeNode* cur = root;
        while(cur) {
            if(!cur->left) {
                vec.push_back(cur->val);
                cur = cur->right;
                continue;
            }
            TreeNode* p = cur->left;
            while(p->right && p->right != cur) p = p->right;
            
            if(!p->right) {
                vec.push_back(cur->val);
                p->right = cur;
                cur = cur->left;
            }
            else {
                p->right = nullptr;
                cur = cur->right;
            }
            
        }
        return vec;
    }
};

解法一：

1. 递归法其实也用了程序的栈空间，本质上和迭代法是一样的。所以在迭代法中，同样使用一个栈st，初始时栈中只有一个根结点。
2. 在递归的每一层里，从栈中取出栈顶元素，读取值。随后将其右子结点推入栈，再将其左子结点入栈；
3. 栈空时，说明遍历完成。

解法二：

这个解法描述比较绕，看leetcode官方题解莫里斯遍历。

2019/12/21 14:12