二叉树的遍历

• 前序遍历 Leetcode preorder
• 中序遍历 Leetcode inorder
• 后续遍历 Leetcode postorder
• Morris Traversal

前序遍历

递归

时间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> res;
    vector<int> preorderTraversal(TreeNode* root) {
        preorder(root);
        return res;
    }

private:
    void preorder(TreeNode* root) {
        if (!root) {
            return;
        }
        
        res.push_back(root->val);
        preorder(root->left);
        preorder(root->right);
    }
};

非递归

时间O(n), 空间O(n)

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        if (!root) {
            return res;
        }
        
        s.push(root);
        while (!s.empty()) {
            TreeNode* curt = s.top();
            s.pop();
            
            res.push_back(curt->val);                    // access the curret node
            if (curt->right) s.push(curt->right);   // push right child to stack
            if (curt->left) s.push(curt->left);        // push left child to stack, left child will be poped out first
        }
        return res;
    }
};

中序遍历

递归

class Solution {
public:
    vector<int> res;
    vector<int> inorderTraversal(TreeNode* root) {
        inorder(root);
        return res;
    }
private:
    void inorder(TreeNode *node) {
        if (!node) {
            return;   
        }
        
        inorder(node->left);
        res.push_back(node->val);
        inorder(node->right);
    }
};

非递归

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> res;

        while (!s.empty() || root) {
            if (root) {
                s.push(root);
                root = root->left;
            } else {
                root = s.top(); s.pop();
                res.push_back(root->val);
                root = root->right;
            }
        }
        return res;
    }
};

后序遍历

递归

vector<int> res;
    void postorder(TreeNode *node) {
        if (!node) {
            return;
        }
        
        postorder(node->left);
        postorder(node->right);
        res.push_back(node->val);
    }

非递归

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode *p, *last;    // 记录当前结点与上次访问结点
        p = root;

        do {
            while (p) {                // 一路往左下走
                s.push(p);
                p = p->left;
            }
            last = NULL;
            while (!s.empty()) {
                p = s.top(); s.pop();
                if (p->right == last) { // 当右孩子不存在 或者 右孩子是上次访问结点，可访问当前结点。
                    res.push_back(p->val);  // 后序遍历中右孩子在当前结点前一位被访问
                    last = p;
                } else {
                    s.push(p);        // 反之，当前结点二次进栈 （右孩子没被访问）
                    p = p->right;   // 进入右树
                    break;
                }
            }
        } while (!s.empty());
        return res;
    }
};

Morris Traversal

时间 O(n), 空间 O(1)

Morris 中序

中序遍历中一个结点的前驱为： 左子树最右下角的结点。后继：右子树最最下角的结点

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        TreeNode *curt, *pre;
        curt = root;
        while (curt) {
            if (curt->left) {
                pre = curt -> left;
                while (pre->right && pre->right != curt) {        // 寻找前驱
                    pre = pre->right;
                }
                
                if (pre->right == NULL) {
                    pre->right = curt;     // 将前驱的右孩子指向当前结点
                    curt = curt->left;
                } else if (pre->right == curt) {  // 恢复前驱右孩子
                    res.push_back(curt->val);
                    pre->right = NULL;
                    curt = curt->right;
                }
            } else {
                res.push_back(curt->val);
                curt = curt->right;
            }
        }
        return res;
    }
};

Morris 先序

前序的右孩子作为标记，如果为空代表左子树没有访问，反之则已经访问过

/**
 * 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> res;
        TreeNode *pre, *curt;
        curt = root;
        while (curt) {
            if (curt -> left) {
                pre = curt->left;
                while (pre->right && pre->right != curt) {
                    pre = pre->right;
                }
                if (!pre->right) {
                    res.push_back(curt->val);    // 与中序Morris唯一不同，在这里输出
                    pre->right = curt;
                    curt = curt->left;
                } else if (pre->right == curt) {
                    pre->right = NULL;
                    curt = curt->right;
                }
            } else {
                res.push_back(curt->val);
                curt = curt->right;
            }
        }
        return res;
    }
};