輸入一個整數數組，判斷該數組是不是某二叉搜索樹的后序遍歷結果。如果是則返回?true，否則返回?false。假設輸入的數組的任意兩個數字都互不相同。

?

參考以下這顆二叉搜索樹：

? ? ?5
? ? / \
? ?2 ? 6
? / \
?1 ? 3
示例 1：

輸入: [1,6,3,2,5]
輸出: false
示例 2：

輸入: [1,3,2,6,5]
輸出: true
?

提示：

數組長度 <= 1000

思路：找到第一個比根大的數字x，x右邊所有數字都要比根大才符合定義。

然后對左右子樹重復上述過程。

class Solution {int[] postorder;public boolean verifyPostorder(int[] postorder) {this.postorder=postorder;return verify(0, postorder.length - 1); }// 遞歸實現private boolean verify(int left, int right){if (left >= right) return true;int rootValue = postorder[right]; // 當前根// 找出第一個大于根節點的，右邊必須都在右子樹中int k = left;while (k < right && postorder[k] < rootValue){ k++;}//判斷for (int i = k; i < right; i++){if (postorder[i] < rootValue) return false;}return verify(left, k - 1) && verify(k, right - 1);}
}

---

輸入一棵二叉樹和一個整數，打印出二叉樹中節點值的和為輸入整數的所有路徑。從樹的根節點開始往下一直到葉節點所經過的節點形成一條路徑。

?

示例:
給定如下二叉樹，以及目標和?sum = 22，

? ? ? ? ? ? ? 5
? ? ? ? ? ? ?/ \
? ? ? ? ? ? 4 ? 8
? ? ? ? ? ?/ ? / \
? ? ? ? ? 11 ?13 ?4
? ? ? ? ?/ ?\ ? ?/ \
? ? ? ? 7 ? ?2 ?5 ? 1
返回:

[
? ?[5,4,11,2],
? ?[5,8,4,5]
]

提示：

節點總數 <= 10000

思路：深搜+回溯

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {List<List<Integer>> ans=new ArrayList();List<Integer> temp=new ArrayList();public List<List<Integer>> pathSum(TreeNode root, int sum) {help(root,sum);return ans;}public void help(TreeNode root, int sum){if(root==null)return;temp.add(root.val);sum-=root.val;if(sum==0 && root.left==null && root.right==null){ans.add(new ArrayList(temp));}help(root.left,sum);help(root.right,sum);temp.remove(temp.size() - 1);}
}

---

請實現 copyRandomList 函數，復制一個復雜鏈表。在復雜鏈表中，每個節點除了有一個 next 指針指向下一個節點，還有一個 random 指針指向鏈表中的任意節點或者 null。

示例 1：

輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：

輸入：head = [[1,1],[2,1]]
輸出：[[1,1],[2,1]]
示例 3：

輸入：head = [[3,null],[3,0],[3,null]]
輸出：[[3,null],[3,0],[3,null]]
示例 4：

輸入：head = []
輸出：[]
解釋：給定的鏈表為空（空指針），因此返回 null。
?

提示：

-10000 <= Node.val <= 10000
Node.random?為空（null）或指向鏈表中的節點。
節點數目不超過 1000 。

思路：先把每個節點后面復制一個相同的節點，為了方便處理好random。然后再分開即可。

空間O(1)

/*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}
*/
class Solution {public Node copyRandomList(Node head) {if (head == null) {return head;}//將拷貝節點放到原節點后面，例如1->2->3這樣的鏈表就變成了這樣1->1'->2'->3->3'for (Node node = head, copy = null; node != null; node = node.next.next) {copy = new Node(node.val);copy.next = node.next;node.next = copy;}//把拷貝節點的random指針安排上for (Node node = head; node != null; node = node.next.next) {if (node.random != null) {node.next.random = node.random.next;}}//分離拷貝節點和原節點，變成1->2->3和1'->2'->3'兩個鏈表，后者就是答案Node newHead = head.next;for (Node node = head, temp = null; node != null && node.next != null;) {temp = node.next;node.next = temp.next;node = temp;}return newHead;}
}

---

序列化是將一個數據結構或者對象轉換為連續的比特位的操作，進而可以將轉換后的數據存儲在一個文件或者內存中，同時也可以通過網絡傳輸到另一個計算機環境，采取相反方式重構得到原數據。

請設計一個算法來實現二叉樹的序列化與反序列化。這里不限定你的序列 / 反序列化算法執行邏輯，你只需要保證一個二叉樹可以被序列化為一個字符串并且將這個字符串反序列化為原始的樹結構。

示例:?

你可以將以下二叉樹：

? ? 1
? ?/ \
? 2 ? 3
? ? ?/ \
? ? 4 ? 5

序列化為 "[1,2,3,null,null,4,5]"
提示:?這與 LeetCode 目前使用的方式一致，詳情請參閱?LeetCode 序列化二叉樹的格式。你并非必須采取這種方式，你也可以采用其他的方法解決這個問題。

說明:?不要使用類的成員 / 全局 / 靜態變量來存儲狀態，你的序列化和反序列化算法應該是無狀態的。

思路：我們普通的遍歷（前序中序后序）序列，通常是不能唯一確定一個二叉樹的，需要前中結合或者后中結合。是因為我們不知道哪里可以停止，比如例子中：到3時，我們不知道該掛到2的下面還是2兩邊都是null（3應該掛1的右邊）。解決方法就是把所有的null記錄下來，比如例子中的二叉樹：前序：1，2，null，null，3，4，null，null，5，null，null。下面是在這種做法的實現。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
public class Codec {public String serialize(TreeNode root) {      //用StringBuilderreturn ser_help(root, new StringBuilder()).toString();}public StringBuilder ser_help(TreeNode root, StringBuilder str){if(null == root){str.append("null,");return str;}str.append(root.val); str.append(",");str = ser_help(root.left, str);str = ser_help(root.right, str);return str;}public TreeNode deserialize(String data) {List<String> list_word = new LinkedList<String>(Arrays.asList(data.split(",")));return deser_help(list_word);}public TreeNode deser_help(List<String> li){if(li.get(0).equals("null")){li.remove(0);return null;}TreeNode res = new TreeNode(Integer.valueOf(li.get(0)));li.remove(0);res.left = deser_help(li);res.right = deser_help(li);return res;}
}// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

?