36. 二叉搜索树与双向链表

剑指 Offer 36. 二叉搜索树与双向链表

思路:中序遍历+双指针
class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(root==nullptr) return root;
        stack<Node*> stk;
        while(root!=nullptr){
            stk.push(root);
            root=root->left;
        }
        Node* prev=nullptr,*head;
        while(stk.size()){
            Node* cur=stk.top();
            stk.pop();
            if(prev==nullptr)
                head=cur;
            else{
                prev->right=cur;
                cur->left=prev;
            }
            prev=cur;
            if(cur->right) {
                cur=cur->right;
                //注意要遍历所有的左子树
                while(cur!=nullptr){
                    stk.push(cur);
                    cur=cur->left;
                }
            }
        }
        prev->right=head;
        head->left=prev;
        return head;
    }
};

时间复杂度 O(N) N是二叉树的节点数

空间复杂度 O(N)

Morris中序遍历

流程如下:

  1. 如果cur为空,停止遍历
  2. 如果cur不为空:
    1. 如果cur的左节点为空,打印cur值,然后让cur指向右子节点
    2. 如果cur有左子节点,则让左子节点找到最右边的结点pre
      1. 如果pre的右子节点为空,让pre的右子节点指向cur,即pre->right=cur,然后cur指向左子节点,即cur=cur->left
      2. 如果pre的右子节点不为空,则让它指向空,即pre->right=nullptr,然后输出cur的值,并将cur指向右子节点,即cur=cur->right

具体可以看下二叉树的Morris中序和前序遍历

先序遍历和中序遍历只是访问结点的时机不同,先序遍历在步骤2访问左子树之前访问根节点,中序遍历在访问左子树后访问右子树前访问根节点,具体步骤如下:

  1. 如果cur为空,停止遍历
  2. 如果cur不为空:
    1. 如果cur的左节点为空,然后让cur指向右子节点
    2. 如果cur有左节点,则让左子节点找到最右边的结点pre
      1. 如果pre的右子节点为空,让pre的右子节点指向cur,打印cur值,然后cur指向左子节点
      2. 如果pre的右子节点不为空,则让它指向空,然后指向右子结点
class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(root==nullptr) return root;
        Node* prev=nullptr,*cur=root,*head;
        while(cur!=nullptr){
            if(cur->left==nullptr){
                if(prev==nullptr){
                    head=cur;
                }else{
                    prev->right=cur;
                }
                cur->left=prev;
                prev=cur;
                cur=cur->right;
            }else{
                Node* preTree=cur->left;
                while(preTree->right!=nullptr&&preTree->right!=cur){
                    preTree=preTree->right;
                }
                if(preTree->right==nullptr){
                    preTree->right=cur;
                    cur=cur->left;
                }else{
                    preTree->right=nullptr;
                    prev->right=cur;
                    cur->left=prev;
                    prev=cur;
                    cur=cur->right;
                }
            }
        }
        head->left=prev;
        prev->right=head;
        return head;
    }
};

时间复杂度 O(n)

空间复杂度 O(1)

上一篇:FreeRTOS与RT-Thread对于中断及临界区的处理


下一篇:【leetcode】另一棵树的子树 c++