CC150小結資料結構

數組與字元串

二叉堆可以用數組來表示

如大頂堆，建構的過程為從下到上。每次出現子節點大于父節點，旋轉，然後對目前節點的子樹進行遞歸處理，列印出排序的堆的時間複雜度為，nlog(n).

1.1确定一個字元串的所有字元是否全都不同。

思路：采用boolean數組進行緩存，ASCII與Unicode，考慮進去長度的因素256個，大于肯定會出現重複，時間複雜度O(n)。

1.2用c或者c++實作void reverse（char* str），反轉一個null結尾的字元串。

思路：不使用額外的空間就可以實作，這個是雙指針。

這裡給出程式

void reverse(char *str){
    char *end = str;
    char temp;
    if (str){
        while(*end){
            ++end;
        }
        --end;
        while (str < end){
            temp = *str;
            *str++ = *end;
            *end-- = temp;
        }
    }
}
           

1.3給定兩個字元串,請編寫程式，确定其中一個字元串重新排列後能否變成另外的一個字元串。

思路：先去定細節，變位詞Dog與God疏忽是同一個字元串，空格出現算不算，String.trim()去除首尾的空格。

解法1：可以先對字元串進行排序處理，String.toCharArray()，java.util.Arrays.sort()方法

解法2：假設為ASCII碼，那麼用int數組記錄第一個字串出現的次數，當第二字元串字元出現次數大于第一個出現次數時，傳回false。第一個字元串使用toCharArray的方法，第二個使用charAt（）。

1.4編寫方法，将字元串中的空格全部替換為“%20”。

思路：字元串的操作，這個要進行兩次周遊，先進行一次得到數組中空字元串的個數，然後再進行處理。從尾部開始，避免資料丢失。

這裡給出代碼：

public void replaceSpace(char[] str, int length){
    int spacenum = , newlength, i;
    for(i = ; i < length; i++){
        if (str[i] == ' '){
            spacenum++;
        }
    }
    newlength = length + spacenum * ;
    str[newlength] = '\n';//結束标志位
    int index = newlength - ;
    for (i = length - ; i > ; i--){
        if (str[i] != ' '){
            str[index--] = str[i];
        } else {
            str[index--] = '0';
            str[index--] = '2';
            str[index--] = '%';
        }
    }
}
           

1.5利用字元重複出現的次數，編寫一個方法，實作基本的字元串的壓縮功能。比如，字元串“aabcccccaaa”會變為a2b1c5a3。若壓縮後沒有變短，就傳回原字元串。

思路：采用StringBuffer，按照規則進行統計，最後進行長度統計。

1.6給定一幅N*N矩陣表示的圖像，其中每個像素的大小為4個位元組，編寫一個方法，将圖像旋轉90度。不占用額外的空間。

思路：進行一層層的旋轉，對每一層進行環狀旋轉。用first來定義每一個環的最小下标，last表示最小标志，offset做緩存。

public static void rotate(int[][] num) {
         int len = num.length;
         for (int layer = ; layer < len / ; layer++){
             int first = layer;
             int last = len -  - first;
             for (int i = first; i < last; i++){
                 int offset = i - first;
                 int top = num[first][i];
                 //左轉上
                 num[first][i] = num[last - offset][first];
                 //下轉左
                 num[last - offset][first] = num[last][last - offset];
                 //右轉下
                 num[last][last - offset] = num[i][last];
                 //上轉右
                 num[i][last] = top; 
             }
         }
    }
           

1.7編寫一個方法，若M*N矩陣中某個元素為0，則将其所在的行與列清零。

思路：這是一個陷阱題，首先用兩個booelan類型的數組進行歸零行以及列的标記，下一步再進行清零操作。

1.8假定有一個方法isSubString，給定兩個字元串s1與s2，編寫代碼檢查s2是否由s1旋轉組成，隻能調用一次isSubString的方法。

思路：out of box方法，假定s1 = xy = waterbottle,x = wat, y = terbottle,s2 = yx =erbottlemat,yx 肯定是xyxy的子串。先進行長度的判定，長度不同，肯定傳回false，然後利用子串進行判定。

public boolean isRotation(String s1, String s2) {
    if (s1 == null && s2 == null) return false;
    if (s1 == null || s2 == null) return true;
    int len = s1.length();
    if (len == s2.length() && len > ) {
        String s1s1 = s1 + s1;
        return isSubstring(s1s1, s1);
    }
    return false;
}
           

連結清單

連結清單這塊需要注意dummy的使用

2.1 編寫代碼，移除未排序連結清單中的重複節點。進階：如果不使用緩沖區，該怎麼解決？

思路：利用散清單記錄，有一個函數需要掌握，containsKey(),同時注意連結清單的删除操作，要有previous的緩存。

public void deleteDups(LinkedListNode n){
    Hashtable table = new Hashtable();
    LinkedListNode previous = null;
    while (n != null){
        if (table.containsKey(n.data)){
            previous.next = n.next;
        } else {
            table.put(n.data, true);
            previous = n;
        }
        n = n.next;
    }
}
           

不使用緩存區，就得采用兩個指針進行疊代處理

2.2實作一個算法，找出單向連結清單中倒數第k個結點。

思路：用先行指針的方法

2.3實作一個算法，删除單向連結清單中間的某個結點，假定你隻能通路該結點。

思路：将目前結點的下一個結點的值複制到目前結點，然後删除下一個結點。

2.4編寫代碼，以給定值x為基準将連結清單分割成兩部分，所有小于x的結點排在大于或等于x的結點之前。

思路：這個是采用建立兩個連結清單，然後進行合并處理的方式。

java中的super()方法是針對父類來說的。

2.5給定兩個用連結清單表示的整數，每個節點包含一個數位。這些數位是反向存放的也就是個位排在連結清單的首部。編寫函數對這兩個整數求和，并利用連結清單形式傳回結果。

示例 ： 輸入 （7-> 1 -> 6） + ( 5 -> 9 -> 2) ,即617 + 295 與普通的加法保持一緻 輸出 2-> 1-> 9 ,即912.

這個采用的是普通的加法進行處理。

進階 ：假設這些數位是正向存放的，請再做一遍。

這個是要用到遞歸進行處理，需要注意兩個數的位數不相等。

2.6給定一個有環連結清單，實作一個算法傳回環路的開頭結點。

有環連結清單的定義，在連結清單中的某個結點的next元素指向在它前面出現過的結點，則表明連結清單存在環路。

示例

輸入： A->B ->C->D->E->C (C結點出現了兩次)

那麼傳回：C 結點

思路：設定兩個指針，fast與slow，假設從第s個結點，進入到環路，那麼當slow在s結點的時候，fast處于2s結點，讓大S為 S = s mod loop_size,此時，fast與slow相差S步，在loop_size - S 步以後，fast 與 slow相遇，碰撞結點距離環路開始的位置為S，（對于slow來說，走了loop_size - S步，那麼loop_size- （loop_size- S））此時碰撞結點距離環路起始處的距離為s個結點，連結清單開始位置也是距離起始處s個結點，那麼兩個指針方向同時出發，會相交于環路起始結點。

public static LinkedListNode getBegainHead(LinkedListNode head){
        LinkedListNode fast = head;
        LinkedListNode slow = head;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow){
                break;
            }
        }
        if (fast == null || fast.next == null){
            return null;
        }
        slow = head;
        while (slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
           

這是一個很經典的方法。

2.7 編寫一個函數，檢查連結清單是否為回文。

思路：先行指針，取到中間位置的數，用stack來存儲資料，注意長度為奇數，根據fast指向的内容即可判斷。

棧與隊列

3.2請設計一個棧，除push與pop方法，還支援min方法，可傳回棧元素中的最小值。push、pop、min方法的時間複雜度為O(1)。

思路：1.新封裝 一個對象，對象中包含 value 以及 min，在stack中進行存儲。注意super.調用父類方法，peek（）檢視棧頂元素

2.與以上類似，設計子類，繼承Stack，子類中增加新的Stack用于存儲出現變化的最小值，入棧操作時進行比較，出棧操作時進行更新。

3.4經典漢諾塔問題

思路：利用stack的資料類型做資料存儲

遞歸方法求解：

public void moveDisks(int n, Tower origin, Tower destination, Tower buffer){
    if (n <= ) return;
    moveDisks(n -, origin, buffer, destination);
    moveTop(origin, destination);
    moveDisks(n - , buffer, destination, origin);
}
           

3.5實作一個MyQuene類，該類用兩個棧來實作一個隊列

思路：兩個棧，一個為new，另外一個為old。隊列add資料為new push資料，隊列出資料，從old pop資料，如果old 為空，則将new出棧，old入棧。

兩個隊列實作棧的話，

class MyStack {
    private Queue<Integer> inquene = new LinkedList<Integer>();
    private Queue<Integer> outquene = new LinkedList<Integer>();
    int temp =;
    // Push element x onto stack.
    public void push(int x) {
        inquene.add(x);
    }
    // Removes the element on top of the stack.
    public void pop() {
      if ( inquene.isEmpty()){
          while (!outquene.isEmpty()){
              temp = outquene.peek();
              outquene.poll();
              if( !outquene.isEmpty() ){
                  inquene.add(temp);
              }
          }  
      } else {
            while (!inquene.isEmpty()){
                 temp = inquene.peek();
                  inquene.poll();
                  if( !inquene.isEmpty() ){
                      outquene.add(temp);
                  }
            }
        }
    }
    // Get the top element.
    public int top() {
        if( inquene.isEmpty() ){
            while( !outquene.isEmpty() ){
                  temp = outquene.peek();
                  outquene.poll();
              }
            return temp;
        }else{
             while(  !inquene.isEmpty() ){
                temp = inquene.peek();
                inquene.poll();
                outquene.add(temp);
            }
             return temp;
        }       
    }
    // Return whether the stack is empty.
    public boolean empty() {
        return inquene.isEmpty()&&outquene.isEmpty();
    }
}
           

3.6經典的stack排序問題，按照升序對棧進行排序。最多隻能使用一個額外的棧存放臨時資料。

思路：建立一個棧，

//注意給定兩個while指針的使用
public Stack<Integer> stackSort(Stack<Integer> s1){
    Stack<Integer> s2 = new Stack<Integer>();
    while (!s1.isEmpty()){
        Integer temp = s1.pop();
        while(!s2.isEmpty() && s2.peek() > temp){// 本次while循環保證temp是目前s2裡面最小的那個
            s1.push(s2.pop());
        }
        s2.push(temp);// 
    }
    return s2;
}
           

樹與圖

樹的三種周遊方式，前序周遊，中序周遊，後序周遊等，遞歸形式的實作以及使用棧與隊列疊代形式的實作。用V表示父節點，L表示左子節點，R表示右子節點，則VLR表示先序周遊，LVR表示中序周遊，LRV表示後序周遊。在處理時，按照遞歸的思想，對每一個結點都進行順序上的檢查處理。前序，中序，後序是根據中間結點被通路的相對順序來說的。

判斷圖是否有環：

針對無向圖可以采用并查集來判斷是否有環：
class GraphCycle{
     int V, E;    // V-> no. of vertices & E->no.of edges
     Edge edge[]; // /collection of all edges

     class Edge {//edges
         int src, dest;
     };

     // Creates a graph with V vertices and E edges
     GraphCycle(int v,int e){
         V = v;
         E = e;
         edge = new Edge[E];
         for (int i=; i<e; ++i)
             edge[i] = new Edge();
     }

     // A utility function to find the subset of an element i
     int find(int parent[], int i){
         if (parent[i] == -)
             return i;
         return find(parent, parent[i]);
     }

     // A utility function to do union of two subsets
     void Union(int parent[], int x, int y){
         int xset = find(parent, x);
         int yset = find(parent, y);
         parent[xset] = yset;
     }


     // The main function to check whether a given graph
     // contains cycle or not
     int isCycle( GraphCycle graph) {
         // Allocate memory for creating V subsets
         int parent[] = new int[graph.V];

         // Initialize all subsets as single element sets
         for (int i=; i<graph.V; ++i)
             parent[i]=-;

         // Iterate through all edges of graph, find subset of both
         // vertices of every edge, if both subsets are same, then
         // there is cycle in graph.
         for (int i = ; i < graph.E; ++i) {
             int x = graph.find(parent, graph.edge[i].src);
             int y = graph.find(parent, graph.edge[i].dest);

             if (x == y && x != -)
                 return ;
             graph.Union(parent, x, y);
         }
         return ;
     }  
           

針對有向圖，采用的是dfs加上标記位來做
      public boolean canFinish(int numCourses, int[][] prerequisites) {
            HashSet<Integer>[] edges = new HashSet[numCourses];
            for (int i =  ; i < numCourses; i++) {
                edges[i] = new HashSet<Integer>();
            }
            for (int[] temp : prerequisites) {
                HashSet a = edges[temp[]];
                a.add(temp[]);
            }
            for (int i = ; i < numCourses; i++) {
                boolean[] visit = new boolean[numCourses];
                boolean[] resTack = new boolean[numCourses];
                Arrays.fill(visit, false);
                Arrays.fill(resTack, false);
                if (isRecyle(i, edges, visit, resTack)) {
                    return false;
                }
            }
            return true;
      }
      public boolean isRecyle(int i,HashSet<Integer>[] edges, boolean[] visit, boolean[] resTack) {
          if (visit[i] == false) {
              visit[i] = true;
              resTack[i] = true;
              HashSet<Integer> pre = edges[i];
              for (int id : pre) {
                  if (! visit[id] && isRecyle(id,edges, visit, resTack) ) {
                      return true;
                  } else if (resTack[id]) {
                      return true;
                  }
              }
          }
          resTack[i] = false;
          return false;
      }
           

圖的周遊

深度優先搜尋

// 遞歸版本
void DFSsearch（Node root）{
    if (root == null){
        return;
    }
    visit(root);
    root.isvisited = true;
    foreach (Node n in root.adjacent){
        search(n);
    }
}
//疊代版本,與樹的前序周遊類似，先通路本節點的内容，右邊入棧，左邊入棧
void DFSearch(Node root){
    if (root == null){
        return; 
    }
    Stack<Node> stack = new Stack(root);
    stack.push(root);
    Node temp = null;
    while(stack.size() > ){
        temp = stack.pop();
        if (root.right != null){
            stack.push(root.right)
        }
        if （root.left != null）{
            stack.push(root.left);
        }
    }
}
//廣度優先的話，就采用隊列的形式
void search(Node root){
    if (null == root){
        return;
    }
    Quene<Node> que = new LinkedList<Node>();
    root.visited = true;
    visit(root);
    que.add(root);
    Node temp = null;
    while (que.size() > ){
        temp = que.remove();
        for (Node n in temp.adjacent){
            visit(n);
            n.visited = true;
            que.add(n);
        }
    }
}
           

注意substring（a, b）;從0開始，包含a，但是不包含b。

遞歸版樹的周遊

前序vlr

public void trvelPre(TreeNode root){
    if (null == root){
        retrun;
    }
    visit(root.data);
    trvelPre(root.left);
    trvelPre(root.right);
}
中序lvr以及後續lrv隻是修改遞歸的後三條語句就可以

           

疊代版的周遊

前序周遊
public void trvelPre(TreeNode root){
    if (null == root){
        return;
    }
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    while(!stack.isEmpty()){
        TreeNode temp = stack.pop();
        visit(temp);
        if (null != temp.right){
            stack.push(temp.right);
        }
        if (null != temp.left){
            stack.push(temp.left);
        }
    }
}
中序周遊，對于完備的樹，可以得到parent，空間複雜度為O()，非完備的就先不這樣處理
public void trvelIn(TreeNode root){
        if (null == root){return;}
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode temp = root;
        //中序周遊方式有所不同，碰到左節點就入棧，左節點通路完成後，轉向右子節點
        while (true){
            if (temp != null){
                stack.push(temp);
                temp = temp.left;
            } else if (!stack.isEmpty()){
                temp = stack.pop();
                System.out.print(temp.val);
                temp = temp.right;
            } else {
                break;
            }
        }
}
後序周遊
public void vistiafter(TreeNode root) {  
        if (null == root ){return;}
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode temp = root;
        stack.push(temp);
        while (!stack.isEmpty()){
            if ((stack.peek().left != temp) && (stack.peek().right != temp)){
                //目前temp結點既不表示棧頂元素的左節點也不表示右節點，
                //temp棧頂元素的左兄弟結點或者是root結點
                // 表示切換子樹
                getHLVFL(stack.peek(), stack);
            }
            temp = stack.pop();
            System.out.print(temp.val);
        }
    }
    public void getHLVFL(TreeNode temp, Stack<TreeNode> stack){
        while(null != temp){
            if (null != temp.left){
                if (null != temp.right){
                    stack.push(temp.right);
                }
                stack.push(temp.left);
            } else {
                stack.push(temp.right);
            }
            temp = stack.peek();
        }
        stack.pop();
    }
    後序周遊結束
           

根據vlr以及lvr，得到lrv，構造出樹

public TreeNode getaf(String pre, String in ,int len){
        TreeNode node = new TreeNode();
        if(len == ){
            return null;
        }
        char root = pre.charAt();
        int index = ;
        for(int i = ; i < len; i++){
            if(root == in.charAt(i)){
                index = i;
                break;
            }
        }
        node.val = root;
        node.left = getaf(pre.substring(,index + ), in.substring(, index), index );
        node.right = getaf(pre.substring(index + , len), in.substring(index + , len), len - index - );
        System.out.println(root);//這條語句放的位置，可以輸出不同的周遊順序，現在是後序，最上面是前序，放到中間就是中序
        return node;
    }
//root.right = bulidHelp(pre, in, preroot + index - left + 1, index + 1, right);對兩邊的進行處理
           

圖的DFS深度優先周遊，BFS廣度優先周遊,要使用到隊列

4.1檢查二叉樹是否平衡，任意一個結點，其兩棵子樹的高度差不超過1

思路：遞歸得到樹的高度，遞歸判斷每一個結點是否平衡

public int checkHeight(TreeNode root){
    if (null == root){
        return ;
    }
    int leftHeight = checkHeight(root.left);
    if (leftHeight == -){
        return -;
    }
    int rightHeight = cheakHeight(root.right);
    if (rightHeight == -){
        return -;
    }
    if (Math.abs(leftHeight - rightHeight) > ){
        return -;
    } else {
        return Math.max(leftHeight, rightHeight) + ;
    }
}
public boolean isBlance(TreeNode tree){
    if (checkHeight(tree) == -){
        return fasle;
    } else {
        return true;
    }
}
           

4.2給定一個有向圖，找出兩個節點之間是否存在一條路徑

廣度優先搜尋适合查找最短路徑

public enum State{
    Unvisited, Visited, Visiting;
}
public static boolean search(Graph g, Node start, Node end){
    if (null == g || null == start){
        return false;
    }
    LinkedList<Node> list = new LinkedList<Node>();
    for (Node u : g.getNodes()){
        u.state = State.Unvisited;
    }
    list.add(start);
    start.state = State.Visiting;
    Node u = null;
    while(!list.isEmpty()){
        u = q.removeFirst();
        if (u != null){
            for (Node v : u.getAdjacent()){
                if (v.state == State.Unvisited){
                    if (v == end){
                        return true;
                    } else {
                        v.state = State.Visiting;
                        q.add(v);
                    }
                }
            }
            u.state = State.Visited;
        }
    }
    return false;
}
           

4.3給定一個有序整數數組，元素個不相同，并且按照升序排列，編寫算法建立高度最小的二叉查找樹。

使處于中間位置上的元素更靠近根節點。

public TreeNode createMin(int nums, int start, int end){
    if (start > end){
        return null;
    }
    int mid = start + ((end - start) >> );
    TreeNode temp = new TreeNode(nums[mid]);
    temp.left = createMin(nums, start, mid - );
    temp.right = createMin(nums, mid + , end);
    return temp;
}
public TreeNode createMinBFS(int[] nums){
    return createMin(nums, , nums.length - );
}
           

4.4給定一個二叉樹，建立含有某一深度上的所有結點的連結清單，比如一棵樹的深度為D，建立D個連結清單。

思路：對廣度優先的算法進行稍微修改，一層一層增加即可。

4.5檢查一課二叉樹是否為二叉查找樹

思路：1.如果不存在相等的樹，所有左結點小于等于目前結點，目前結點小于右結點，current.left.val<= current.val < current.right.val(程式也可以這麼寫)。改進，遞歸

public static int last_printed = integer.MIN_VALUE;
public boolean checkBFS(TreeNode root){
    if (null == root){return true;}
    if (!checkBFS(root.left)){
        return false;
    }
    if (root.val <= last_printed){// 右側的必須大于
        return false;
    }
    last_printed = temp.val;
    if (!checkBFS(root.right)){
        return false;
    }
    return true;
}
           

思路2,利用最大最小算法，遞歸，限定目前結點的數的範圍，與數學上的夾逼準則類似

public boolean checkMaxMinBFS(TreeNode root, int min, int max){
    if (null == root){return true;}
    if (root.val <= min || root.val > max){
        return false;
    }
    if (!checkMaxMinBFS(root.left, min, root.val) || !checkMaxMinBFS(root.right, root.val, max)){
        return false;
    }
    return true;
}
public boolean checkBFS(TreeNode root){
    return checkMaxMinBFS(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
#
           

4.6找出二叉查找樹的下一個結點（可以得到父節點）

思路：也就是中序周遊的下一個結點，此時要分開讨論

public TreeNode leftMostChild(TreeNode root){
    if (null == root){return null;}
    while(root.left != null){
        root = root.left;
    }
    return root;
}
public TreeNode inorderSucc(TreeNode n){
    if (null == n){return null;}
    if(n.right != null){
        return leftMostChild(n.right);
    } else {
        TreeNode cu = n;
        TreeNode pa = cu.parent;
        while (pa != null && pa.left != cu){
            cu = pa;
            pa = cu.parent;
        }
        return pa;
    }
}
           

4.7 找出二叉樹中兩個結點的第一個共同祖先。不得将額外的結點存儲在資料結構中

思路：1.從根結點調用cover方法，先檢查是否都在根結點中，不在的話傳回null，然後依次調用，left與right，

2.遞歸，優化常數時間 傳回值依次為 傳回p，root子樹包含p不包含q；傳回q，root子樹中包含q不包含p；傳回null，都不包含；否則傳回 p與q的共同祖先。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q)  return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null)   return root;
        return left != null ? left : right;
    }
     // 非遞歸版本的，時間複雜度挺高的。
       public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, TreeNode> parents = new HashMap<TreeNode, TreeNode>();
        Queue<TreeNode > queue  = new LinkedList<>();
        parents.put(root, null);
        queue.offer(root);
        TreeNode temp = null;
        while (!parents.containsKey(p) || !parents.containsKey(q)) {
            temp = queue.poll();
            if (temp.left != null) {
                parents.put(temp.left, temp);
                queue.offer(temp.left);
            }
            if (temp.right != null) {
                parents.put(temp.right, temp);
                queue.offer(temp.right);               
            }
        }
        Set<TreeNode> anc = new HashSet<>();
        while (p != null) {
            anc.add(p);
            p = parents.get(p);
        }
        while (!anc.contains(q)) {
            q = parents.get(q);
        }
        return q;
    }
           

4.8你有一顆非常大的二叉樹：T1，有幾百萬個結點；T2有幾百個結點。設計一個算法，判斷T2是不是T1的子樹

思路1：對兩個樹前序以及中序周遊，判斷T2是不是T1的子串，注意null補全特殊的字元

2：遞歸調用

public boolean treeMatch(TreeNode a, TreeNode b){
    if (a == null && b == null){
        return true;
    }
    if (a == null || b == null){
        return false;
    }
    if (a.val != b.val){
        return false;
    }
    return (treeMatch(a.left, b.left) && treeMatch(a.right, b.right));
}
public boolean isSubTree(TreeNode t1, TreeNode t2){
    if (null == t1 && null == t2){
        return true;
    }
    if (t1 == null){
        return false;
    }
    if (t1.val == t2.val){
        if (treeMatch(t1, t2)){return true;}
    }
    return (isSubTree(t1.left, t2) || isSubTree(t1.right, t2));
}
           

4.9給定一個二叉樹，其中每一個結點都含有一個數值。設計一個算法，列印某個結點數值總和等于某個給定值的所有路徑。

思路：從根節點出發進行計算