恢復二進制搜索樹


難度級別
經常問 亞馬遜 ByteDance Microsoft微軟 神諭 尤伯杯
二進制搜索樹 二叉樹 深度優先搜索

考慮一個二叉搜索樹,該樹的兩個節點已交換,設計了一種恢復二叉搜索樹的算法。

考慮下面給出的二進制搜索樹,其兩個節點已被交換為輸入。

恢復二進制搜索樹

BST上的錯誤節點被檢測到(突出顯示),然後交換以獲取正確的BST。

恢復二進制搜索樹

下面是交換不正確的節點後獲得的更正的輸出BST。

恢復二進制搜索樹

恢復二進制搜索樹的解決方案類型

  1. 幼稚
  2. 遞歸
  3. 迭代
  4. 莫里斯遍歷

 

幼稚

恢復二進制搜索樹的方法

使用向量按順序存儲樹的所有元素 遍歷,對向量進行排序。 再次,對樹進行有序遍歷,並將排序後的向量中的值一個接一個地分配給樹節點。

算法

  1. 執行樹的有序遍歷並將遍歷存儲在動態數組中。
  2. 動態排序 排列 使用插入排序(以最小化複雜度)。
  3. 再次執行有序遍歷,並將節點值更改為已排序數組中的值。
  4. 返回更正後的二進制搜索樹的根節點。

恢復二進制搜索樹

履行

C ++程序
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// blueprint of the tree node
class Node
{
    public : 
    int data;
    Node *left, *right, *next;
    
    Node(int key)
    {
        data = key;
        left = right = next = NULL;
    }
};

// function that performs inorder traversal based on the mode
/*
Their are 3 modes : 
1. traversal ('t') : simply perform traversal
2. storage ('s') : store data of tree into a vector
3. modify ('m'): store data of vector into a tree
*/
void inorder(Node *root,vector <int> &arr,char mode)
{
    if(!root)
    return;
    
    inorder(root->left,arr,mode);
    if(mode == 't')
    cout<<root->data<<" ";
    else if(mode == 's')
    arr.push_back(root->data);
    else if(mode == 'm')
    {
        int n = arr.size();
        root->data = arr[n-1];
        arr.pop_back();
    }
    inorder(root->right,arr,mode);
}

// function that corrects the BST and returns it's root
Node* fixBST(Node *root)
{
    // array to store inorder traversal
    vector <int> arr;
    // store the inorder traversal into arr
    inorder(root,arr,'s');
    
    // apply insertion sort to arr
    // insertion sort is used to minimize time complexity to o(n)
    int i,j,key; 
    for (i = 1; i < arr.size(); i++) 
    { 
        key = arr[i]; 
        j = i - 1; 
        while (j >= 0 && arr[j] < key) 
        { 
            arr[j + 1] = arr[j]; 
            j = j - 1; 
        } 
        arr[j + 1] = key; 
    } 
    
    // perform inorder on tree and modify the the node value of tree
    inorder(root,arr,'m');
    return root;
}


int main()
{
    /* create the incorrect BST*/
    Node *root = new Node(4);
    root->left = new Node(7);
    root->right = new Node(6);
    root->left->left = new Node(1);
    root->left->right = new Node(3);
    root->right->left = new Node(5);
    root->right->right = new Node(2);
    
    vector <int> arr;
    
    cout<<"Inorder traversal before : ";
    inorder(root,arr,'t');
      
    root = fixBST(root);
    
    cout<<endl;
    
    cout<<"Inorder traversal after : "; 
    inorder(root,arr,'t');
    return 0;
}
Inorder traversal before : 1 7 3 4 5 6 2 
Inorder traversal after : 1 2 3 4 5 6 7
Java程序
import java.util.*;
import java.io.*;

class tutorialCup
{
    // blueprint of the tree node
    static class Node
    {
        int data;
        Node left, right, next;
        
        Node(int key)
        {
            data = key;
            left = right = next = null;
        }
    }

    // function that performs inorder traversal based on the mode
    /*
    Their are 3 modes : 
    1. traversal ('t') : simply perform traversal
    2. storage ('s') : store data of tree into a vector
    3. modify ('m'): store data of vector into a tree
    */
    static void inorder(Node root,ArrayList <Integer> arr,char mode)
    {
        if(root == null)
        return;
        
        inorder(root.left,arr,mode);
        if(mode == 't')
        System.out.print(root.data+" ");
        else if(mode == 's')
        arr.add(root.data);
        else if(mode == 'm')
        {
            int n = arr.size();
            root.data = arr.get(n-1);
            arr.remove(n-1);
        }
        inorder(root.right,arr,mode);
    }
    
    // function that corrects the BST and returns it's root
    static Node fixBST(Node root)
    {
        // array to store inorder traversal
        ArrayList <Integer> arr = new ArrayList<>();
        // store the inorder traversal into arr
        inorder(root,arr,'s');
        
        // apply insertion sort to arr
        // insertion sort is used to minimize time complexity to o(n)
        int i,j,key; 
        for (i = 1; i < arr.size(); i++) 
        { 
            key = arr.get(i); 
            j = i - 1; 
            while (j >= 0 && arr.get(j) < key) 
            { 
                arr.set(j+1,arr.get(j)); 
                j = j - 1; 
            } 
            arr.set(j+1,key); 
        } 
        
        // perform inorder on tree and modify the the node value of tree
        inorder(root,arr,'m');
        return root;
    }
    
    public static void main (String[] args) 
    {
        /* create the incorrect BST*/
        Node root = new Node(4);
        root.left = new Node(7);
        root.right = new Node(6);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.left = new Node(5);
        root.right.right = new Node(2);
        
        ArrayList <Integer> arr = new ArrayList<>();
        
        System.out.print("Inorder traversal before : ");
        inorder(root,arr,'t');
        
        root = fixBST(root);
        
        System.out.println();
        System.out.print("Inorder traversal after : ");         
        inorder(root,arr,'t');
    }

}
Inorder traversal before : 1 7 3 4 5 6 2 
Inorder traversal after : 1 2 3 4 5 6 7

恢復二叉搜索樹的複雜度分析

  • 時間複雜度:T(n)= O(n)
  • 空間複雜度:A(n)= O(n)

遞歸

恢復二進制搜索樹的方法

  1. 考慮 在上面的示例中給出。 BST的節點可以通過兩種方式交換。
  2. 1st方式:交換了2個非相鄰樹節點(即這些節點之間至少有一個節點。例如:交換非相鄰節點的樹的有序遍歷為:1 7 3 4 5 6 2.正如我們觀察到的2和7從各自的位置調換。
    1. 我們執行順序遍歷並使用 第一 第二 變量以存儲兩個錯誤放置的節點。 我們用 上一頁 存儲在當前節點之前訪問的上一個節點 (根) 有序遍歷期間的節點。
    2. 在順序遍歷期間,我們發現一個違反BST順序的節點。 即prev-> data> root-> data(其中root是要訪問的當前節點),我們將prev存儲到第一個,然後將root存儲到第二個。
    3. 在進一步遍歷期間,如果我們發現另一個違反BST標準的節點(如上所述),但是這次已經為第一個節點分配了一個值。 因此,我們將當前節點分配給第二個節點。
    4. 遍歷結束後,我們交換存儲在第一節點和第二節點中的數據。
  3. 2nd方式:交換了2個相鄰節點(即,節點是父子對)。例如:交換相鄰節點的樹的有序遍歷為:1 2 4 3 5 6 7.正如我們觀察到的,從其交換了3和4各自的職位。
    1. 我們執行順序遍歷並使用 第一 第二 變量以存儲兩個錯誤放置的節點。 我們用 上一頁 存儲在當前節點之前訪問的上一個節點 (根) 有序遍歷期間的節點。
    2. 在順序遍歷期間,我們發現一個違反BST順序的節點。 即prev-> data> root-> data(其中root是要訪問的當前節點),我們將prev存儲到第一個,然後將root存儲到第二個。
    3. 遍歷結束後,我們交換存儲在第一節點和第二節點中的數據。

算法

  1. 定義prev(遍歷存儲先前的節點),first(無序存儲第一個節點),second(無序存儲第二個節點)變量以存儲各種樹節點地址。
  2. 執行簡單的順序遍歷。
  3. 如果在順序遍歷期間,我們發現一個違反BST順序的節點。 即prev-> data> root-> data.we將prev存儲到 第一 並紮根 第二。
  4. 在進一步遍歷期間,如果發現另一個違反BST標準的節點,即prev-> data> root-> data。 但是這一次已經為第一個節點分配了一個值。 所以我們將當前節點分配給 第二。
  5. 執行順序遍歷後。 交換第一個和第二個節點的數據。樹是固定的。

恢復二進制搜索樹

履行

C ++程序
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// blueprint of the tree node
class Node
{
    public : 
    int data;
    Node *left, *right, *next;
    
    Node(int key)
    {
        data = key;
        left = right = next = NULL;
    }
};
/* function that performs inorder traversal 
and checks for the incorrectly set nodes*/
void inorderFix(Node *root,Node* &prev,Node* &first,Node* &second)
{
    if(root == NULL)
    return;
    
    inorderFix(root->left,prev,first,second);
    
    if(prev != NULL && prev->data > root->data)
    {
        // first misordering found
        if(first == NULL)
        {
            first = prev;
            second = root;
        }
        
        // second misordering found (if exists)
        else
        second = root;
    }
    
    prev = root;
    
    inorderFix(root->right,prev,first,second);
}
// function that corrects the BST and returns it's root
Node* fixBST(Node *root)
{
    Node *prev,*first,*second;
    prev = first = second = NULL;
    
    inorderFix(root,prev,first,second);
    swap(first->data,second->data);
    
    return root;
}

// function to simply perform inorder traversal of the tree
void inorder(Node *root)
{
    if(root == NULL)
    return;
    
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
}

int main()
{
    /* create the incorrect BST*/
    Node *root = new Node(4);
    root->left = new Node(7);
    root->right = new Node(6);
    root->left->left = new Node(1);
    root->left->right = new Node(3);
    root->right->left = new Node(5);
    root->right->right = new Node(2);
    
    cout<<"Inorder traversal before : ";
    inorder(root);
    
    root = fixBST(root);
    cout<<endl;
    
    cout<<"Inorder traversal after : ";
    inorder(root);
    
    return 0;
}
Inorder Traversal before : 1 7 3 4 5 6 2 
Inorder Traversal after : 1 2 3 4 5 6 7
Java程序
import java.util.*;
import java.io.*;

class tutorialCup
{
    // blueprint of the tree node
    static class Node
    {
        int data;
        Node left, right, next;
        
        Node(int key)
        {
            data = key;
            left = right = next = null;
        }
    }

    /* function that performs inorder traversal 
    and checks for the incorrectly set nodes*/
    static void inorderFix(Node root,ArrayList <Node> nodes)
    {
        if(root == null)
        return;
        
        inorderFix(root.left,nodes);
        
        if(nodes.get(0) != null && nodes.get(0).data > root.data)
        {
            // first misordering found
            if(nodes.get(1) == null)
            {
                // first is set to previous
                nodes.set(1,nodes.get(0));
                // second is set to current node
                nodes.set(2,root);
            }
            // second misordering found (if exists)
            else
            nodes.set(2,root);
        }
        
        // 1st element of ArrayList stores previous nodes
        nodes.set(0,root);
        
        inorderFix(root.right,nodes);
    }
    // function that corrects the BST and returns it's root
    /*
    here,
    prev -> nodes.get(0)
    first -> nodes.get(1)
    second -> nodes.get(2)
    */
    static Node fixBST(Node root)
    {
        // we use ArrayList to store previous(nodes[0]),first(nodes[1]) and second(nodes[2])
        // initially all nodes are set to null
        ArrayList <Node> nodes = new ArrayList<>(Arrays.asList(null,null,null));
        inorderFix(root,nodes);
        
        // swap the values of the nodes
        int temp = nodes.get(1).data;
        nodes.get(1).data = nodes.get(2).data;
        nodes.get(2).data = temp;
        
        return root;
    }
    
    // function to simply perform inorder traversal of the tree
    static void inorder(Node root)
    {
        if(root == null)
        return;
        
        inorder(root.left);
        System.out.print(root.data+" ");
        inorder(root.right);
    }
    
    public static void main (String[] args) 
    {
        /* create the incorrect BST*/
        Node root = new Node(4);
        root.left = new Node(7);
        root.right = new Node(6);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.left = new Node(5);
        root.right.right = new Node(2);
        
        System.out.print("Inorder Traversal before : ");
        inorder(root);
        
        root = fixBST(root);
        System.out.println();
        
        System.out.print("Inorder Traversal after : ");
        inorder(root);
        
    }
}
Inorder Traversal before : 1 7 3 4 5 6 2 
Inorder Traversal after : 1 2 3 4 5 6 7

恢復二叉搜索樹的複雜度分析

  • 時間複雜度:T(n)= O(n)
  • 空間複雜度:A(n)= O(n),使用的遞歸堆棧空間。

迭代

恢復二進制搜索樹的方法

這個想法是將上面的遞歸代碼轉換成迭代代碼。

算法

  1. 定義prev(遍歷存儲先前的節點),first(無序存儲第一個節點),second(無序存儲第二個節點)變量以存儲各種樹節點地址。
  2. 執行簡單的順序遍歷。
  3. 如果在順序遍歷期間,我們發現一個違反BST順序的節點。 即prev-> data> root-> data.we將prev存儲到 第一 並紮根 第二。
  4. 在進一步遍歷期間,如果發現另一個違反BST標準的節點,即prev-> data> root-> data。 但是這一次已經為第一個節點分配了一個值。 所以我們將當前節點分配給 第二。
  5. 執行順序遍歷後。 交換第一和第二節點的數據。 樹是固定的。

履行

C ++程序
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// blueprint of the tree node
class Node
{
    public : 
    int data;
    Node *left, *right, *next;
    
    Node(int key)
    {
        data = key;
        left = right = next = NULL;
    }
};
 
// function that corrects the BST by performing iterative inorder 
// and returns it's root
Node* fixBST(Node *root)
{
    Node *prev,*first,*second;
    prev = first = second = NULL;
    
    Node* curr = root;
    
    stack <Node*> st;
    
    while(!st.empty() ||  root != NULL)
    {
        if(root != NULL)
        {
            // visit current node's (root) left subtree
            st.push(root);
            root = root->left;
        }
        else
        {
            // done left subtree of current node
            root = st.top();
            st.pop();
            
            // compare root.val with root.val if we have one
            if(prev != NULL && root->data < prev->data)
            {
                // incorrect smaller node is always found as prev node
                if(first == NULL) 
                first = prev;
                
                // incorrect larger node is always found as current root node
                second = root;         
            }  
            
            // visit root's right subtree
            prev = root;
            root = root->right;
        }
    }
    
    // fix the BST by swapping values
    int temp = first->data;
    first->data = second->data;
    second->data = temp;
    
    // return address of the original root node
    return curr;
}

// function to simply perform inorder traversal of the tree
void inorder(Node *root)
{
    if(root == NULL)
    return;
    
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
}

int main()
{
    /* create the incorrect BST*/
    Node *root = new Node(4);
    root->left = new Node(7);
    root->right = new Node(6);
    root->left->left = new Node(1);
    root->left->right = new Node(3);
    root->right->left = new Node(5);
    root->right->right = new Node(2);
    
    cout<<"Inorder traversal before : ";
    inorder(root);
    
    root = fixBST(root);
    cout<<endl;
    
    cout<<"Inorder traversal after : ";
    inorder(root);
    
    return 0;
}
Inorder Traversal before : 1 7 3 4 5 6 2 
Inorder Traversal after : 1 2 3 4 5 6 7
Java程序
import java.util.*;
import java.io.*;

class tutorialCup
{
    // blueprint of the tree node
    static class Node
    {
        int data;
        Node left, right, next;
        
        Node(int key)
        {
            data = key;
            left = right = next = null;
        }
    }

    // function that corrects the BST and returns it's root
    static Node fixBST(Node root)
    {
        Node prev,first,second;
        prev = first = second = null;
        
        Node curr = root;
        
        Stack<Node> st = new Stack<Node>();
        
        while(!st.isEmpty() ||  root != null)
        {
            if(root != null)
            {
                // visit current node's (root) left subtree
                st.push(root);
                root = root.left;
            }
            else
            {
                // done left subtree of current node
                root = st.pop();
                
                // compare root.val with root.val if we have one
                if(prev != null && root.data <= prev.data)
                {
                    // incorrect smaller node is always found as prev node
                    if(first == null) 
                    first = prev;
                    
                    // incorrect larger node is always found as current root node
                    second = root;         
                }  
                
                // visit root's right subtree
                prev = root;
                root = root.right;
            }
        }
        
        // fix the BST by swapping values
        int temp = first.data;
        first.data = second.data;
        second.data = temp;
        
        // return address of the original root node
        return curr;
    }
    
    // function to simply perform inorder traversal of the tree
    static void inorder(Node root)
    {
        if(root == null)
        return;
        
        inorder(root.left);
        System.out.print(root.data+" ");
        inorder(root.right);
    }
    
    public static void main (String[] args) 
    {
        /* create the incorrect BST*/
        Node root = new Node(4);
        root.left = new Node(7);
        root.right = new Node(6);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.left = new Node(5);
        root.right.right = new Node(2);
        
        System.out.print("Inorder Traversal before : ");
        inorder(root);
        
        root = fixBST(root);
        System.out.println();
        
        System.out.print("Inorder Traversal after : ");
        inorder(root);   
    }
}
Inorder Traversal before : 1 7 3 4 5 6 2 
Inorder Traversal after : 1 2 3 4 5 6 7

恢復二叉搜索樹的複雜度分析

  • 時間複雜度:T(n)= O(n)
  • 空間複雜度:A(n)= O(n)

莫里斯遍歷

恢復二進制搜索樹的方法

這個想法是基本上執行樹的有序Morris遍歷。 莫里斯遍歷可確保遍歷在線性時間和恆定空間(甚至沒有遞歸堆棧空間)中進行。

Morris遍歷類似於遞歸/迭代遍歷,但是我們需要在遍歷期間修改樹結構。 在訪問根的左樹之前,我們將在左樹中最右邊的節點與根之間建立一條後沿。 因此,遍歷左側樹後,我們可以返回到根節點。

然後,我們再次在左側子樹中找到最右邊的節點,剪切後邊緣,恢復樹結構,然後開始訪問右側子樹。

錯誤樹節點的檢測類似於遞歸/迭代情況。

算法

  1. 執行Morris遍歷並按順序處理每個節點。
  2. 對於每個節點(樹的最左邊的節點除外),請跟踪其上一個節點 上一頁。 當前正在處理的節點存儲在 發生。
  3. 如果在遍歷期間,我們發現一個違反BST順序的節點。 即prev-> data> root-> data.we將prev存儲到 第一 並紮根 第二。
  4. 在進一步遍歷期間,如果我們發現另一個違反BST標準的節點,即prev-> data> root-> data。 但是從那以後,第一個節點已經被分配了一個值。 所以我們將當前節點(違反BST標準)分配給 第二。
  5. 執行順序遍歷後。 交換的數據 第一第二 節點和樹變得固定。

履行

C ++程序
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// blueprint of the tree node
class Node
{
    public : 
    int data;
    Node *left, *right, *next;
    
    Node(int key)
    {
        data = key;
        left = right = next = NULL;
    }
};
 
// function that corrects the BST by performing iterative inorder 
// and returns it's root
Node* fixBST(Node *root)
{
    Node *prev,*first,*second;
    prev = first = second = NULL;
    
    // stores rightmost node in left subtree of root
    Node* rightMost = NULL;
    // stores current node starting with root node 
    Node* curr = root;
    
    while(curr != NULL)
    {
        // for each node, we compare it with prev node as we did in in-order-traversal
        if(prev != NULL && curr->data < prev->data)
        {
            if(first == NULL) 
            first = prev;
            
            second = curr;
        }
        
        if(curr->left != NULL)
        {
            // got left tree, then let's locate its rightmost node in left tree
            rightMost = curr->left;
            // we may have visited the left tree before, and connect the rightmost node with curr node (root node)
            while(rightMost->right != NULL && rightMost->right != curr)
                rightMost = rightMost->right;
            
            if(rightMost->right == curr)
            {
                // if this left tree has been visited before, then we are done with it
                // cut the connection with currNode and start visit curr's right tree
                rightMost->right = NULL;
                prev = curr;
                curr = curr->right;
            }
            else
            {
                // if this left tree has not been visited before, then we create a back edge from rightmost node
                // to curr node, so we can return to the start point after done the left tree
                rightMost->right = curr;
                curr = curr->left;
            }
            
        }
        else
        {
            // no left tree, then just visit its right tree
            prev = curr;
            curr = curr->right;
        }
    }
    
    // swap the values of incorrect nodes
    swap(first->data,second->data);
    return root;
}

// function to simply perform inorder traversal of the tree
void inorder(Node *root)
{
    if(root == NULL)
    return;
    
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
}

int main()
{
    /* create the incorrect BST*/
    Node *root = new Node(4);
    root->left = new Node(7);
    root->right = new Node(6);
    root->left->left = new Node(1);
    root->left->right = new Node(3);
    root->right->left = new Node(5);
    root->right->right = new Node(2);
    
    cout<<"Inorder traversal before : ";
    inorder(root);
    
    root = fixBST(root);
    cout<<endl;
    
    cout<<"Inorder traversal after : ";
    inorder(root);
    
    return 0;
}
Inorder Traversal before : 1 7 3 4 5 6 2 
Inorder Traversal after : 1 2 3 4 5 6 7
Java程序
import java.util.*;
import java.io.*;

class tutorialCup
{
    // blueprint of the tree node
    static class Node
    {
        int data;
        Node left, right, next;
        
        Node(int key)
        {
            data = key;
            left = right = next = null;
        }
    }

    // function that corrects the BST using morris traversal and returns it's root
    static Node fixBST(Node root)
    {
        Node prev,first,second;
        prev = first = second = null;
        
        // stores rightmost node in left subtree of root
        Node rightMost = null;
        // stores current node starting with root node 
        Node curr = root;
        
        while(curr != null)
        {
            // for each node, we compare it with prev node as we did in in-order-traversal
            if(prev != null && curr.data < prev.data)
            {
                if(first == null) 
                first = prev;
                
                second = curr;
            }
            
            if(curr.left != null)
            {
                // got left tree, then let's locate its rightmost node in left tree
                rightMost = curr.left;
                // we may have visited the left tree before, and connect the rightmost node with curr node (root node)
                while(rightMost.right != null && rightMost.right != curr)
                    rightMost = rightMost.right;
                
                if(rightMost.right == curr)
                {
                    // if this left tree has been visited before, then we are done with it
                    // cut the connection with currNode and start visit curr's right tree
                    rightMost.right = null;
                    prev = curr;
                    curr = curr.right;
                }
                else
                {
                    // if this left tree has not been visited before, then we create a back edge from rightmost node
                    // to curr node, so we can return to the start point after done the left tree
                    rightMost.right = curr;
                    curr = curr.left;
                }
                
            }
            else
            {
                // no left tree, then just visit its right tree
                prev = curr;
                curr = curr.right;
            }
        }
        
        // swap the values of incorrect nodes
        int temp = first.data;
        first.data = second.data;
        second.data = temp;
        
        return root;
    }
    
    // function to simply perform inorder traversal of the tree
    static void inorder(Node root)
    {
        if(root == null)
        return;
        
        inorder(root.left);
        System.out.print(root.data+" ");
        inorder(root.right);
    }
    
    public static void main (String[] args) 
    {
        /* create the incorrect BST*/
        Node root = new Node(4);
        root.left = new Node(7);
        root.right = new Node(6);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.left = new Node(5);
        root.right.right = new Node(2);
        
        System.out.print("Inorder Traversal before : ");
        inorder(root);
        
        // fixing the BST
        root = fixBST(root);
        System.out.println();
        
        System.out.print("Inorder Traversal after : ");
        inorder(root);   
    }
}
Inorder Traversal before : 1 7 3 4 5 6 2 
Inorder Traversal after : 1 2 3 4 5 6 7

恢復二叉搜索樹的複雜度分析

  1. 時間複雜度:T(n)= O(n)
  2. 空間複雜度:A(n)= O(1),也不使用數據結構,也不使用遞歸堆棧空間。

參考