第二十三題：二叉搜索樹的后續(xù)遍歷序列
難易度：??
輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果
如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。
對(duì)于一個(gè)二叉搜索樹而言，例如：
該二叉搜索樹的后續(xù)遍歷的結(jié)果為：
9,13,11,20,32,30,16
不難看出，后續(xù)遍歷的序列中，最后一個(gè)數(shù)字為一個(gè)二叉搜索樹的root節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)為root節(jié)點(diǎn)的右子樹，從后向前遍歷，遍歷到第一個(gè)小于root.val的那個(gè)節(jié)點(diǎn)為root節(jié)點(diǎn)的左子樹。這樣通過捋順后續(xù)遍歷序列當(dāng)中有什么規(guī)律后，可以想到，我們應(yīng)該使用遞歸的思想。要說明的是，二叉樹和遞歸真的密不可分，因?yàn)?，二叉樹的遍歷就是遞歸。
本題的代碼如下：
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence == null || sequence.length == 0){
return false;
}
return process(sequence,0,sequence.length - 1);
}
public boolean process(int[] arr,int start,int end){
if(end <= start){
return true;
}
int i = start;
for(;i < end;i++){
if(arr[i] > arr[end]){
break;
}
}
for(int j = i;j < end;j++){
if(arr[j] < arr[end]){
return false;
}
}
return process(arr,start,i - 1)&& process(arr,i,end - 1);
}
}
第二十四題：二叉樹中和為某一值的路徑
難易度：???
給出二叉樹的TreeNode 類
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
輸入一顆二叉樹的根節(jié)點(diǎn)和一個(gè)整數(shù)，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑
路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑
如示例：
當(dāng)target = 22 時(shí)，共有兩條路徑即：10 ->5 ->7與 10 ->12
先上代碼：
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
ArrayList<ArrayList<Integer>> listAll = new ArrayList<>();
ArrayList<Integer> list = new ArrayList<>();
int sum = 0;
process(root,target,listAll,list,sum);
return listAll;
}
public void process(TreeNode node,int target,ArrayList<ArrayList<Integer>> listAll,ArrayList<Integer> list,int sum){
if(node == null){
return;
}
sum += node.val;
if(node.left == null && node.right == null){
if(sum == target){
list.add(node.val);
listAll.add(new ArrayList(list));
list.remove(list.size() - 1);
}
return;
}else{
list.add(node.val);
process(node.left,target,listAll,list,sum);
process(node.right,target,listAll,list,sum);
list.remove(list.size() - 1);
}
}
}
前序遍歷二叉樹，同時(shí)使用一個(gè)變量來記錄從頭節(jié)點(diǎn)一直到尾節(jié)點(diǎn)的和，如果遍歷到尾節(jié)點(diǎn)，和不等于target則說明這一條路徑不是節(jié)點(diǎn)和相加為target的路徑。如果遍歷到了尾節(jié)點(diǎn)，和等于target 那么我們就將這個(gè)序列添加到保存ArrayList的listAll中。在前序遍歷二叉樹的時(shí)候，我們使用了棧這種數(shù)據(jù)結(jié)構(gòu)，本題使用了ArrayList,為了保證每次遍歷到下一個(gè)節(jié)點(diǎn)的時(shí)候不重復(fù)，所以在每個(gè)過程結(jié)束的時(shí)候，要使用ArrayList模擬stack.pop()這個(gè)功能即：
list.remove(list.size() - 1);
本題的思路不太好想清楚，要知道，sum統(tǒng)計(jì)的是每一條鏈的和，最開始寫這個(gè)代碼的時(shí)候在list.remove()操作后，我想將sum 再減去當(dāng)前節(jié)點(diǎn)的值，但這樣就錯(cuò)了。因?yàn)閷?shí)質(zhì)是每一條鏈都獲得了相應(yīng)鏈節(jié)點(diǎn)的和 sum。應(yīng)該重點(diǎn)去感受本題的計(jì)算過程。
