- 二叉搜索樹(shù)的后序遍歷序列
以數(shù)組｛5坡氯，7晨横，6，9箫柳，11手形，10，8｝為例悯恍，后序遍歷結(jié)果的最后一個(gè)數(shù)字8就是根節(jié)點(diǎn)的值库糠。在這個(gè)數(shù)組中，前3個(gè)數(shù)字5涮毫，7和6都比8小瞬欧，是值為8的結(jié)點(diǎn)的左子樹(shù)結(jié)點(diǎn)贷屎；后3個(gè)數(shù)字9，11和10都比8 大艘虎，是值為8的結(jié)點(diǎn)的右子樹(shù)結(jié)點(diǎn)
于是呢唉侄，如果只有兩個(gè)或者1個(gè)數(shù)，定義為是真的野建。具體實(shí)現(xiàn)上属划，先找左邊第一個(gè)比跟節(jié)點(diǎn)（也就是最后一個(gè)點(diǎn)）大的值，如果此后的點(diǎn)還存在比根節(jié)點(diǎn)小的值候生，那么就是假的嘍榴嗅，繼續(xù)遞歸實(shí)現(xiàn)。
public static boolean VerifySquenceOfBST(int[] arr) {
if(arr==null || arr.length==0) return false;
return verify(arr,0,arr.length-1);
}
public static boolean verify(int[] arr,int start,int end) {
if(end-start<=1) return true;
int cur = start;
//找到比跟節(jié)點(diǎn)大的地方
while(arr[cur]<arr[end] && cur<end) {
cur++;
}
//后面的節(jié)點(diǎn)一旦比根節(jié)點(diǎn)還小陶舞，就說(shuō)明不是右子樹(shù)
for(int i = cur+1;i<end;i++) {
if(arr[i]<arr[end]) return false;
}
return verify(arr, start, cur - 1) && verify(arr, cur, end - 1);
}
- 二叉樹(shù)中和為某一值的路徑
遞歸的實(shí)現(xiàn)嗽测，棧彈入彈出的時(shí)機(jī)選擇還蠻妙，測(cè)試數(shù)據(jù)時(shí)候猜測(cè)+試驗(yàn)出來(lái)肿孵，理解了一下結(jié)果
//二叉樹(shù)中和為某一值的路徑
public static void findpath(TreeNode root, int target) {
if (root == null)
return;
Stack<Integer> path = new Stack<Integer>();
findpathcore(root, target, path);
}
public static void findpathcore(TreeNode root, int target, Stack<Integer> path) {
if (root == null)
return;
//注意push即pop的位置唠粥，要在判斷外邊，這樣彈出時(shí)候能彈出到最外層停做，蠻抽象晤愧，再看時(shí)候可能會(huì)更理解……
path.push(root.val);
if (root.left == null && root.right == null) {
if (target == root.val) {
//path.push(root.val);
for (int i : path) {
System.out.print(i + " ");
}
System.out.println(" ");
}
} else {
//path.push(root.val);
findpathcore(root.left, target - root.val, path);
findpathcore(root.right, target - root.val, path);
//path.pop();
}
path.pop();
}
