【Day 11 LeetCode】二叉树的遍历

标签：11 遍历 cur vector right 二叉树 ans root Day

一、二叉树的遍历

二叉树的遍历主要分为深度优先遍历和广度优先遍历。
深度优先是先往深处走，走到尽头返回；广度优先遍历是一层一层往下遍历。其中，深度优先遍历对应三种顺序，前序、中序、后序遍历，特点也很好记，就是根节点的位置。根节点位于前面就是前序，遍历顺序为根节点-左子树-右子树；相应的，中序遍历的顺序是左子树-根节点-右子树，后序遍历的顺序是左子树-右子树-根节点。
深度优先遍历可以采用递归法或迭代法实现，时空复杂度都是 O ( n ) O(n) O(n)（迭代法需要用栈来记录父节点，递归需要调用系统堆栈，所以空间复杂度是 O ( n ) O(n) O(n)）。
还有一种特殊的算法叫做Morris遍历，其思想是将空闲右子树的节点指向父节点，从而不需要记录父节点，空间复杂度为 O ( 1 ) O(1) O(1)。
下面介绍使用递归、迭代和Morris三种方法的深度优先遍历和迭代方法的广度优先遍历。

1、深度优先遍历–递归写法

前序遍历

class Solution {
    void dfs(TreeNode* node, vector<int> &ans){
        if(node==nullptr)
            return;
        // 前序  根-左-右
        ans.push_back(node->val);
        dfs(node->left, ans);
        dfs(node->right, ans);
    }
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        dfs(root, ans);
        return ans;
    }
};

中序遍历

class Solution {
    void dfs(TreeNode* node, vector<int> &ans){
        if(node==nullptr)
            return;
        // 中序  左子树-根-右子树
        dfs(node->left, ans);
        ans.push_back(node->val);
        dfs(node->right, ans);
    }
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        dfs(root, ans);
        return ans;
    }
};

后序遍历

class Solution {
    void dfs(TreeNode* node, vector<int> &ans){
        if(node==nullptr)
            return;
        // 后序  左-右-根
        dfs(node->left, ans);
        dfs(node->right, ans);
        ans.push_back(node->val);
    }
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        dfs(root, ans);
        return ans;
    }
};

2、深度优先遍历–迭代写法

迭代写法就是要清楚用栈存节点的目的是为了保存根节点，再根据各个顺序的特点在恰当的时机保存节点值。
前序遍历：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> q;
        vector<int> ans;
        while(root || !q.empty()){
            while(root){
                q.push(root);
                ans.push_back(root->val); // 先根节点
                root = root->left;
            }
            root = q.top();q.pop();
            root = root->right;
        }
        return ans;
    }
};

中序遍历：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> q; // 用栈来记录深度遍历的路径
        vector<int> ans;
        while(root || !q.empty()){
            // 找到这条路径的最左叶节点
            while(root){
                q.push(root);
                root = root->left;
            }
            root = q.top();q.pop();
            ans.push_back(root->val);
            root = root->right; // 左-根-右
        }
        return ans;
    }
};

后序遍历：
当套用中序遍历的迭代版本模板，我始终没想清楚怎么在该基础上写出后序遍历版本。因为上面中序遍历的栈是记录根节点，而后序遍历是根节点的顺序是在最后，再弹出根节点开始右子树时，等遍历完右子树，根节点信息就已经丢失。
需要巧妙的转换一下，后序遍历顺序是左子树-右子树-根，反转一下就是根-右子树-左子树。这下就与前序遍历类似了。就可以用一套遍历套路解决三种顺序了。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> q;
        vector<int> ans;
        while(root || !q.empty()){
            while(root){
                q.push(root);
                ans.push_back(root->val); // 先根节点
                root = root->right;
            }
            root = q.top();q.pop();
            root = root->left;
        }
        reverse(ans.begin(), ans.end()); // 反转
        return ans;
    }
};

3、深度优先遍历–Morris写法

Morris方法的思想是将空闲右子树的节点指向父节点，从而不需要开辟额外的空间记录父节点。需要搞清楚Morris的代码是在哪进入左子树、右子树。
前序遍历

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        TreeNode* cur = root;
        vector<int> ans;
        while(cur){
            if(cur->left){
                TreeNode* pre = cur->left;
                while(pre->right && pre->right != cur)
                    pre = pre->right;
                if(pre->right == nullptr){
                    pre->right = cur;
                    ans.push_back(cur->val);
                    cur = cur->left; // 进入左子树
                }else{
                    cur = cur->right;
                    pre->right = nullptr;
                }
            }else{
                ans.push_back(cur->val);
                cur = cur->right; // 进入右子树
            }
        }
        return ans;
    }
};

中序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        TreeNode* cur = root;
        while(cur){
            if(cur->left){
                TreeNode* pre = cur->left;
                // 找到非空左子树的“前驱节点”
                while(pre->right && pre->right!=cur)
                    pre = pre->right;
                if(pre->right==nullptr){
                    // 让“前驱节点”指向当前节点，本质是 记录该左子树的父节点
                    pre->right = cur;
                    cur = cur->left;
                }else{
                    ans.push_back(cur->val);
                    pre->right = nullptr;
                    cur = cur->right;
                }
            }else{
                ans.push_back(cur->val);
                cur = cur->right;
            }
        }
        return ans;
    }
};

后序遍历
与迭代版本遇到的问题一样，所以先讲前序遍历的版本左右互换，得到顺序为根-右-左的结果，再将结果反转就得到后序遍历结果。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        TreeNode* cur = root;
        vector<int> ans;
        while(cur){
            if(cur->right){
                TreeNode* pre = cur->right;
                while(pre->left && pre->left != cur)
                    pre = pre->left;
                if(pre->left==nullptr){
                    pre->left = cur;
                    ans.push_back(cur->val);
                    cur = cur->right; // 进入右子树
                }else{
                    cur = cur->left;
                    pre->left = nullptr;
                }
            }else{
                ans.push_back(cur->val);
                cur = cur->left; // 进入右子树
            }
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

4、层序遍历

层序遍历思路比较清晰，使用队列记录每一层的节点。
迭代写法：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(root==nullptr)
            return ans;
        deque<TreeNode*> q;
        q.push_back(root);
        while(!q.empty()){
            vector<int> tmp;
            int n = q.size();
            while(n--){
                TreeNode* node = q.front();
                tmp.push_back(node->val);
                q.pop_front();
                if(node->left)
                    q.push_back(node->left);
                if(node->right)
                    q.push_back(node->right);
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};

递归写法(通过在递归函数中传入深度参数实现)：

class Solution {
    void dfs(TreeNode* node, vector<vector<int>> &ans, int depth){
        if(node==nullptr)
            return;
        if(depth==ans.size())
            ans.push_back(vector<int>());
        ans[depth].push_back(node->val);
        dfs(node->left, ans, depth+1);
        dfs(node->right, ans, depth+1);
    }
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        dfs(root, ans, 0);
        return ans;
    }
};

二、写在后面

今天完成了二叉树深度优先遍历三种顺序（前序、中序、后序）的三个方法（递归、迭代、Morris）的编写，还有广度优先遍历的递归和迭代写法。具体思路细节之后有时间补充。

标签：11,遍历,cur,vector,right,二叉树,ans,root,Day
From： https://blog.csdn.net/H2020fighting/article/details/144963235