📉
leetcode-题解
  • leetcode-notes
  • linked-list
    • 2-Add-Two-Numbers
    • 109-Convert-Sorted-List-to-Binary-Search-Tree
    • 19-Remove-Nth-Node-From-End-of-List
    • 92-Reverse-Linked-List-II
    • 142-Linked-List-Cycle-II
    • 83-Remove-Duplicates-from-Sorted-List
    • 61-Rotate-List
    • 148-Sort-List
    • 86-Partition-List
    • 82-Remove-Duplicates-from-Sorted-List-II
    • 138-Copy-List-with-Random-Pointer
    • 328-Odd-Even-Linked-List
    • 23- Merge-k-Sorted-Lists
    • 25-Reverse-Nodes-in-k-Group
  • templates
    • bitmap
    • ologn
    • Morris
    • dp
    • binary-search
    • Maxwindow
    • 递归
    • union
    • graph
    • greedy-algorithm
    • kmp
    • list
    • ordered-list
    • tree
    • Manacher
    • Monotonic-stack
    • big-data
    • sort-Summary
    • Bucket-sort
    • bit-opreation
    • heap-sort
  • arrays
    • others
      • 31-Next-Permutation
      • 66-Plus- One
      • 229-Majority-Element-II
      • 414-Third-Maximum-Number
    • matrix
      • 74-Search-a-2D-Matrix
      • 289-Game-of-Life
    • PrefixOrSuffix
      • 560-Subarray-Sum-Equals-K
      • 238-Product-of-Array-Except-Self
    • 二分法
      • rotated-array-problem
      • D天内送达包裹的能力
      • 162-Find-Peak-Element
      • Minimize-maximum-and-maximize-minimum
    • 多指针
      • 611-Valid-Triangle-Number
      • 228-Summary-Ranges
      • 75-Sort-Colors
      • 18-4Sum
      • 27-Remove-Element
      • 三数之和
      • 26-Remove-Duplicates-from-Sorted-Array
      • 盛最多水的容器
      • 80-Remove-Duplicates-from-Sorted-Array-II
      • 最接近的三数之和
    • array-circle
      • 457-Circular-Array-Loop
      • 287-Find-the-Duplicate-Number
      • 565-Array-Nesting
    • 智力题
      • 73-Set-Matrix-Zeroes
      • 最佳观光组合
    • 几何问题
      • 统计全为1的正方形子矩阵
      • 495-Teemo-Attacking
    • sort
      • 88-Merge-Sorted-Array
      • 57-Insert-Interval
  • tree
    • 105-Construct-Binary-Tree-from-Preorder-and-Inorder-Traversal
    • 230-Kth-Smallest-Element in-a-BST
    • 106-Construct-Binary-Tree-from-Inorder-and-Postorder-Traversal
    • 257-Binary-Tree-Paths
    • 113-Path-Sum-II
    • 96-Unique-Binary-Search-Trees
    • 124-Binary-Tree-Maximum-Path-Sum
    • 103-Binary-Tree-Zigzag-Level-Order-Traversal
    • 426-Convert-Binary-Search-Tree-to-Sorted-Doubly-Linked-List
    • 117-Populating-Next-Right-Pointers-in-Each-Node-II
    • 99-Recover-Binary-Search-Tree
    • 366-Find-Leaves-of-Binary-Tree
    • 337-House-Robber-III
    • 333-Largest-BST-Subtree
    • 298-Binary-Tree-Longest-Consecutive-Sequence
    • 428-Serialize-and-Deserialize-N-ary-Tree
    • 1367-Linked-List-in-Binary-Tree
    • 173-Binary-Search-Tree-Iterator
    • 98-Validate-Binary-Search-Tree
    • 156-Binary-Tree-Upside-Down
    • 404-Sum-of-Lef- Leaves
    • 255-Verify-Preorder-Sequence-in-Binary-Search-Tree
    • 272-Closest-Binary-Search-Tree-Value-II
    • 95-Unique-Binary-Search-Trees-II
    • 222-Count-Complete-Tree-Nodes
    • 431-Encode-N-ary-Tree to-Binary-Tree
    • Lowest-Common-Ancestor-of-a-Binary-Tree
    • 129-Sum-Root-to-Leaf-Numbers
  • recursive
    • 前言
    • 39-Combination-Sum
    • 79-Word-Search
    • 04-Power-Set-LCCI
    • 前言
    • 90-Subsets-II
    • 40-Combination-Sum-II
    • 351-Android-Unlock-Patterns
  • dynamic-programming
    • 276-Paint-Fence
    • 132-Palindrome-Partitioning-II
    • 361-Bomb-Enemy
    • 62-Unique-Paths
    • 376-Wiggle-Subsequence
    • 403-Frog-Jump
    • 32-Longest-Valid-Parentheses
    • 97-Interleaving-String
    • 354-Russian-Doll-Envelopes
    • 279-Perfect-Squares
    • 304-Range-Sum-Query-2D-Immutable
    • 10-Regular-Expression-Matching
    • Paint-House-series
    • 139-Word-Break
    • Best-Time-to-Buy-and-Sell-Stock-series
    • 416-Partition-Equal-Subset-Sum
    • 300-Longest-Increasing-Subsequence
    • 91-Decode-Ways
    • Ugly-Number-series
    • 363-Max-Sum-of-Rectangle-No-Larger-Than-K
    • 368-Largest-Divisible-Subset
    • 63-Unique-Paths-II
    • 312-Burst-Balloons
    • 322-Coin-Change
    • 64-Minimum-Path-Sum
    • 140-Word-Break-II
    • 120-Triangle
    • 72-Edit-Distance
    • House-Robber-series
    • 413-Arithmetic-Slices
    • 174-Dungeon-Game
    • 87-Scramble-String
    • 44-Wildcard-Matching
    • 338-Counting-Bits
    • 152-Maximum-Product-Subarray
    • 375-Guess-Number-Higher-or-Lower-II
  • hash-table
    • 381-Insert-Delete-GetRandom-O(1) - Duplicates-allowed
    • 442-Find-All-Duplicates-in-an-Array
    • 380-Insert-Delete-GetRandom-O(1)
    • 1-Two-Sum
    • 3-Longest-Substring-Without-Repeating-Characters
    • 41-First-Missing-Positive
  • stack
    • Monotonic stack
      • 84-Larges-Rectangle-in-Histogram
      • 42-Trapping-Rain-Water
  • bit-manipulation
    • 08-Draw-Line-LCCI
  • Mysql
    • 185-Department-Top-Three-Salaries
    • 177-N-Highest-Salary
    • 178-Rank-Scores
    • 180-Consecutive-Numbers
  • greedy
    • 56-Merge-Intervals
    • 55-Jump-Game
    • 53-Maximum-Subarray
  • math
    • 357-Count-Numbers-with-Unique-Digits
    • 343-Integer-Break
    • 119-Pascal's-Triangle-II
  • string
    • Palindrome
      • 5-Longest-Palindromic-Substring
      • Manacher
  • sliding-window
    • 209-Minimum-Size-Subarray-Sum
Powered by GitBook
On this page

Was this helpful?

  1. templates

Morris

Morris遍历,应该就是线索二叉树的遍历。 cur为空时,则遍历停止 如果一个节点有左子树,那么一定会来到该节点两次,第一次是第一次遍历,第二次是通过线索来到。

如果一个节点有左子树,则找到左子树的最右节点并且为null,将其指向当前节点,并向左移动。 如果左子树最右节点指向当前节点,则将其置为空,并向右移动 如果一个节点没有左子树,则向右移动

``` c++ "Morris" void Morris(TreeNode head){ if(head==nullptr){ return; } TreeNode cur{head}; TreeNode* most_right{nullptr}; while(cur!=nullptr){ //来到左节点 most_right=cur->left; if(most_right!=nullptr){ //有左子树,则找到最右节点,记得一定是左子树,most_right->right!=cur是为了防止跳出左子树进入右子树 while(most_right->right!=nullptr && most_right->right!=cur){ most_right=most_right->right; } //第一次来到该节点 if(most_right->right == nullptr){ most_right->right=cur; cur=cur->left; //向左移动,直接进入下一次循环 continue; } else{ //第二次来到该节点,将most_right置空,然后向右移动 most_right->right=nullptr; //cur=cur->right; }

    }
    //向右移动
    cur=cur->right;
}

}

没有左子树的点都只会遍历一次,有左子树的点都会遍历两次,但是增加的遍历次数是常数级的,并且没有重复的。所以总的来说总的复杂度仍是`O(N)`,空间为`O(1)`

### Morris先序遍历

对于能够到达两次的节点,在第一次遇见时进行打印,对于只能够到达一次的节点,则直接打印。

``` c++ "Morris"
void MorrisPreOrder(TreeNode* head){
    if(head==nullptr){
        return;
    }
    TreeNode* cur{head};
    TreeNode* most_right{nullptr};
    while(cur!=nullptr){
        //来到左节点
        most_right=cur->left;
        if(most_right!=nullptr){
            //进入到这个分支,就说明能来到该节点两次

            //有左子树,则找到最右节点,记得一定是左子树,most_right->right!=cur是为了防止跳出左子树进入右子树
            while(most_right->right!=nullptr && most_right->right!=cur){
                most_right=most_right->right;
            }
            //第一次来到该节点
            if(most_right->right == nullptr){
                most_right->right=cur;
                cur=cur->left;
                cout<<cur->val<<endl;
                //向左移动,直接进入下一次循环
                continue;
            }
            else{
                //第二次来到该节点,将most_right置空,然后向右移动
                most_right->right=nullptr;
                //cur=cur->right;
            }

        }
        //执行到这,要么第二次来到,要么第一次来到,如果不加else分支,第二次来到cur时也会打印

        //能进入这个分支,说明只能来到cur一次
        else{
            cout<<cur->val<<endl;
        }
        //向右移动
        cur=cur->right;
    }
}

中序遍历时对于能来到自己两次的节点,第二次打印,对于只能到达自己一次的节点,直接打印

``` c++ "Morris" void MorrisPreOrder(TreeNode head){ if(head==nullptr){ return; } TreeNode cur{head}; TreeNode* most_right{nullptr}; while(cur!=nullptr){ //来到左节点 most_right=cur->left; if(most_right!=nullptr){ //有左子树,则找到最右节点,记得一定是左子树,most_right->right!=cur是为了防止跳出左子树进入右子树 while(most_right->right!=nullptr && most_right->right!=cur){ most_right=most_right->right; } //第一次来到该节点 if(most_right->right == nullptr){ most_right->right=cur; cur=cur->left; //向左移动,直接进入下一次循环 continue; } else{ //第二次来到该节点,将most_right置空,然后向右移动 most_right->right=nullptr; //cur=cur->right; }

    }
    //执行到这,要么第二次来到,要么第一次来到,如果不加else分支,第二次来到cur时也会打印
    cout<<cur->val<<endl;

    //向右移动
    cur=cur->right;
}

}

后序遍历:对于只能来到自己一次的节点,什么也不做。对于能来到自己两次的节点,当第二次来到时,**逆序打印** 左子树 的右边界节点。最后**逆序**打印整棵树的右边界(即包含头节点的那一斜线右边界)。

那么如何逆序打印右边界?
逆序就相当于把右边界做链表反转,然后打印链表,然后再反转回来即可。


``` c++ "Morris Post"
void MorrisPostOrder(TreeNode* head){
    if(head==nullptr){
        return;
    }
    TreeNode* cur{head};
    TreeNode* most_right{nullptr};
    while(cur!=nullptr){
        //来到左节点
        most_right=cur->left;
        if(most_right!=nullptr){
            //有左子树,则找到最右节点,记得一定是左子树,most_right->right!=cur是为了防止跳出左子树进入右子树
            while(most_right->right != nullptr && most_right->right!=cur){
                most_right=most_right->right;
            }
            //第一次来到该节点
            if(most_right->right == nullptr){
                most_right->right=cur;
                cur=cur->left;
                //向左移动,直接进入下一次循环
                continue;
            }
            else{
                //第二次来到该节点,将most_right置空,然后向右移动
                most_right->right=nullptr;
                //逆序打印该节点的左数右边界
                PrintEdge(cur->left);
                //cur=cur->right;
            }

        }
        //执行到这,要么第二次来到,要么第一次来到,如果不加else分支,第二次来到cur时也会打印


        //向右移动
        cur=cur->right;
    }
    PrintEdge(head);
}

//逆序打印以head为头的右边界
void PrintEdge(TreeNode* head){
    TreeNode* pre{nullptr},* next{nullptr};
    while(head!=nullptr){
        next=head->right;
        head->right=pre;
        pre=head;
        head=next;
    }
    TreeNode* tail{pre};
    head=pre;
    pre=nullptr;
    while(head!=nullptr){
        cout<<head->val;
        head=head->right;
    }
    //再次反转链表
    while(tail!=nullptr){
        next=tail->right;
        tail->right=pre;
        pre=tail;
        tail=next;
    }
}

什么时候用递归套路什么时候用Morris?

如果需要同时获得左右子树的信息并重新整合时只能使用递归套路。否则就可以使用Morris遍历完成相关的遍历题目。

PreviousolognNextdp

Last updated 4 years ago

Was this helpful?