CS杂物

二叉树的遍历

By lbyxiaolizi 34 Views 39 MIN READ 0 Comments

经历了大半个暑假的摆烂，最终还是想起来学点东西，于是重新回去学完剩下的数据结构和刷刷学学 LeetCode每日一题。

二叉树

二叉树是一种每个节点都最多只有两个子节点的树，通常两个子节点叫做左孩子left和右孩子right，一般根节点root要小于两个孩子节点，并且左子节点小于右子节点。

遍历的问题便出在了想要访问所有节点的时候，或者想要找到二叉树中的某一节点的时候，于是根据二叉树的特性便有了以下四种遍历方式：前序遍历、中序遍历、后序遍历、层序遍历。

其中前三种为 DFS，最后一种为 BFS。

所谓序指的是根节点什么时候被访问，例如：前序为根、左、右；中序为左、根、右；后序为左、右、根。

其中中序遍历最为特殊，因为其遍历结果就是二叉树从小到大的排列。

中序遍历

中序遍历是按照左、根、右的顺序来进行遍历，所以我们在最普通的算法中应该先找到最左边的子节点，然后递归向上。

以 LeetCode 94. 二叉树的中序遍历为例

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

CPP 的实现如下：

递归写法：

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

        vector<int> inorderTraversal(TreeNode* root){
            vector<int> res;
            inorder(root,res);
            return res;
        }
};

此算法提供 O(n)的时间复杂度和空间复杂度。

迭代写法

此外，我们可以通过显式把递归中的栈迭代写出来改为迭代写法。

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

            while (curr!=nullptr||!st.empty()) {
                while (curr!=nullptr) {
                    st.push(curr);
                    curr=curr->left;
                }
                curr=st.top();
                st.pop();
                res.push_back(curr->val);

                curr=curr->right;
            }
            return res;
        }
};

迭代写法同样提供 O(n)的时间复杂度和空间复杂度。

更进一步，我们可以进一步优化从而提供O(1)的空间复杂度，也即 Morris 遍历。

Morris 遍历

Morris 遍历不使用栈，所以这时需要解决的问题是左子树遍历完后应当如何返回根节点，这里用的方法是寻找左子树的最右节点（中序前驱的right）并指向当前节点。

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

        while (curr!=nullptr) {
            if(curr->left==nullptr){
                res.push_back(curr->val);
                curr=curr->right;
            }else {
                TreeNode* predecessor=curr->left;
                while (predecessor->right!=nullptr && predecessor->right != curr) {
                    predecessor=predecessor->right;
                }
                if(predecessor->right==nullptr){
                    predecessor->right=curr;
                    curr=curr->left;
                }else {
                    predecessor->right=nullptr;
                    res.push_back(curr->val);
                    curr=curr->right;
                }
            }
        }
        return res;
    }
};

前序遍历

实现思路几乎一致，cpp 实现如下：

递归

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

        vector<int> preorderTraversal(TreeNode* root){
            vector<int> res;
            preorder(root, res);
            return res;
        }
};

遍历

class Solution1{
  public:
    vector<int> preorderTraversal(TreeNode* root){
        vector<int> res;
        stack<TreeNode*> st;
        TreeNode* curr=root;

        while (curr !=nullptr && !st.empty()) {
            while (curr!=nullptr) {
                res.push_back(curr->val);
                st.push(curr);
                curr=curr->left;
            }
            curr=st.top();
            st.pop();
            curr=curr->right;
        }
        return res;
    }
};

class Solution2{
    public:
        vector<int> preorderTraversal(TreeNode* root){
            vector<int> res;
            if(root==nullptr) return res;

            stack<TreeNode*> st;
            st.push(root);

            while ((!st.empty())) {
                TreeNode* node= st.top();
                st.pop();
                res.push_back(node->val);

                if(node->right){
                    st.push(node->right);
                }
                if(node->left){
                    st.push(node->left);
                }
            }
            return  res;
        }
};

这里的遍历有两种思路，其一为按中序遍历的思路修改而来，其二则是按照直接的前序遍历根、左、右进行遍历。

Morris 遍历

思路一致，只是第一次经过 root 时就立刻访问。

class Solution{
    public:
        vector<int> preorderTraversal(TreeNode* root){
            vector<int> res;
            TreeNode* curr=root;

            while (curr!=nullptr) {
                if(curr->left==nullptr){
                    res.push_back(curr->val);
                    curr=curr->right;
                }else {
                    TreeNode* predecessor=curr->left;
                    while (predecessor->right!=nullptr && predecessor->right!=curr) {
                        predecessor=predecessor->right;
                    }

                    if(predecessor->right==nullptr){
                        res.push_back(curr->val);
                        predecessor->right=curr;
                        curr=curr->left;
                    }else {
                        predecessor->right=nullptr;
                        curr=curr->right;
                    }
                }
            }
            return res;
        }
};

后序遍历

实现思路依旧大致一致，但是难点在根必须在左右节点都访问完最后在倒回去访问

以下为 CPP 实现：

递归

递归依旧不需要考虑太多，先相信即可

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

        vector<int> postorderTraversal(TreeNode* root){
            vector<int> res;
            postorder(root, res);
            return res;
        }
};

遍历

由于必须要按左、右、根的顺序，比较难实现，所以不妨先实现简单的根、右、左，然后反过来。

于是第一种遍历就是用两个栈来实现的，一个栈负责实现根、右、左，另一个栈负责反序。

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

            if(!root) return res;

            stack<TreeNode*> st1;
            stack<TreeNode*> st2;

            st1.push(root);

            while (!st1.empty()) {
                TreeNode* node=st1.top();
                st1.pop();
                st2.push(node);
                if (node->left) {
                    st1.push(node->left);
                }
                if (node->right) {
                    st1.push(node->right);
                }
            }

            while (!st2.empty()) {
                res.push_back(st2.top()->val);
                st2.pop();
            }
            return res;
        }
};

换种想法，我们可以直接用数组的翻转代替一个栈，用一个栈来实现。

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

            if(!root) return res;

            stack<TreeNode*> st;
            st.push(root);

            while (!st.empty()) {
                TreeNode* node = st.top();
                st.pop();

                res.push_back(node->val);

                if(node->left){
                    st.push(node->left);
                }

                if (node->right) {
                    st.push(node->right);
                }
            }
            reverse(res.begin(),res.end());

            return res;
        }
};

但是这种写法没有真正的省掉了一个栈的空间，那能否真正优化呢？可以用记忆化来处理。

栈+prev 指针

如果要真的省去一个栈的话，从根到左节点，在回到根去访问右节点，此时才能访问根节点，所以需要拿一个指针记住上一个处理的节点。

于是可以一路找到最左，在一层一层往上回去～

class Solution{
    public:
        vector<int> postorderTraversal(TreeNode* root){
            vector<int> res;
            stack<TreeNode*> st;
            TreeNode* curr=root;
            TreeNode* prev=nullptr;

            while (curr!=nullptr || !st.empty()) {
                while (curr!=nullptr) {
                    st.push(curr);
                    curr=curr->left;
                }
                TreeNode* node = st.top();
                if(node->right==nullptr || node->right == prev){
                    res.push_back(node->val);
                    st.pop();
                    prev=node;
                }else {
                    curr=node->right;
                }
            }
            return res;
        }
};

Morris 遍历

最后，为了做到O(1)的空间复杂度，我们仍然可以使用 Morris 遍历，但是复杂度增加了不少。

需要经历：

  1. 建一个 dummy 节点
  2. 找 predecessor
  3. 建临时线索
  4. 第二次回来
  5. 反转一段右指针路径
  6. 倒序输出该路径
  7. 回复路径
class Solution{
    public:
        void reversePath(TreeNode* from,TreeNode* to){
            if(from==to) return ;
            TreeNode* x= from;
            TreeNode* y= from->right;
            while (x!=to) {
                TreeNode* z=y->right;
                y->right=x;
                x=y;
                y=z;
            }
        }

        void collectReverse(TreeNode* from,TreeNode* to,vector<int>& res){
            reversePath(from, to);
            TreeNode* node=to;
            while (true) {
                res.push_back(node->val);
                if(node==from) break;
                node=node->right;
            }
            reversePath(to, from);
        }

        vector<int> postorderTraversal(TreeNode* root){
            vector<int> res;
            TreeNode dummy(0);
            dummy.left=root;

            TreeNode* curr=&dummy;
            while (curr) {
                if(!curr->left){
                    curr=curr->left;
                }else {
                    TreeNode* prev=curr->left;
                    while (prev->right &&prev->right!=curr) {
                        prev=prev->right;
                    }
                    if(!prev->right){
                        prev->right=curr;
                        curr=curr->left;
                    }else {
                        collectReverse(curr->left, prev, res);
                        prev->right=nullptr;
                        curr=curr->left;
                    }
                }
            }
            return res;
        }
};

层序遍历

DFS 的三种遍历看完了，接着就到了 BFS 的层序遍历

首先是最最普通的使用队列来完成先进先出的要求，为 BFS 实现

BFS+队列

class Solution{
    vector<vector<int>> levelOrder(TreeNode* root){
        vector<vector<int>> res;
        if(!root) return res;

        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size=q.size();
            vector<int> level;
            for(int i=0;i<size;i++){
                TreeNode* node =q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
            res.push_back(level);
        }
        return res;
    }
};

DFS+depth

此外，DFS 也能够完成这一任务，只需要在经过时记录下节点在第几层，然后 push 进对应层的列表

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

        vector<vector<int>> levelOrder(TreeNode* root){
            vector<vector<int>> res;
            dfs(root,0,res);
            return res;
        }
};

本文由 lbyxiaolizi 原创

采用 CC BY-NC-SA 4.0 协议进行许可

转载请注明出处：https://blog.vh.gs/cs/binary-tree-traversal.html

标签: 算法 数据结构

相关推荐

0 评论

发表评论