每天一道劍指offer-二叉樹中和為某一值的路徑

• 2019 年 10 月 4 日
• 筆記

前言

今天的題目 每天的題目見github(看最新的日期): https://github.com/gzc426 具體的題目可以去牛客網對應專題去找。

昨天的題解

題目

每天一道劍指offer-二叉樹中和為某一值的路徑 來源： https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&tqId=11177&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

題目詳述

輸入一顆二叉樹的跟節點和一個整數，列印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。(注意: 在返回值的list中，數組長度大的數組靠前)

題目詳解

思路

• 遞歸的思想，每次去判斷左子樹的最右邊界是不是大於右子樹的最左邊界，如果大於就不是，如果小於，那麼就再往下遞歸。

程式碼

public class Solution {      ArrayList<ArrayList<Integer>> resultList = new ArrayList<>();      public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {            ArrayList<Integer> list = new ArrayList<>();          FindPath(root,target,0,list);          return resultList;      }      public void FindPath(TreeNode root,int target,int sum,ArrayList<Integer> list)      {          if(root == null)              return;          sum += root.val; //sum不是引用，所以sum在每一層的遞歸中都是不同的值，記錄當前的節點和          list.add(root.val);          if(sum == target && root.left == null && root.right == null)          {//找到這樣的路徑了~              resultList.add(new ArrayList<Integer>(list));//存入結果數組              list.remove(list.size()-1);//找到以後還要接著找啊，所以先把當前最後的葉子節點刪除              return;          }          FindPath(root.left,target,sum,list);//左右子樹遞歸進去去找          FindPath(root.right,target,sum,list);          list.remove(list.size()-1);//這裡左右子樹都找完了，回到了找完的左右子樹的父節點          //由於父節點的左右子樹找完了，所以父節點這裡也沒有用了，把父節點刪除      }  }

程式碼截圖（避免亂碼）