二叉樹的層次遍歷Ⅱ
思路：queue
本題和二叉樹的層序遍歷一模一樣，只不過需要返回其節(jié)點值自底向上的層次遍歷結果。我們只需要在最后使用arrayList.add(0,val)方法即可。
代碼如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null){
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new ArrayList<>();
for(int i = 0; i < size; ++i){
root = queue.poll();
list.add(root.val);
if(root.left != null){
queue.offer(root.left);
}
if(root.right != null){
queue.offer(root.right);
}
}
res.add(0,list);
}
return res;
}
}
時間復雜度分析：O(N)
額外空間復雜度：O(N)
執(zhí)行結果：
將有序數組轉換為二叉搜索樹
思路：recursion
如果輸入的序列是有序的序列，我們自然而言就可以聯想到二叉搜索樹的中序遍歷結果就是由小到大排列的。
那么，首先我們思考一個問題：重構的二叉搜索樹是唯一的嗎？
答案必然是否定的，因為我們可以間接認為，給定了有序的輸入序列，實際上就是給定了二叉搜索樹的中序遍歷的結果，如果只知道中序遍歷的結果是無法準確確定一個唯一的樹的。如果給定了前序遍歷+中序遍歷的結果或者是中序遍歷+后續(xù)遍歷的結果則可以確定一棵唯一的二叉樹，可以參考題目：leetcode105.從前序與中序遍歷序列構造二叉樹,106.從中序與后序遍歷序列構造二叉樹
所以，本題的構建方法必然不是唯一的，這里只給出了遞歸的求解方式，另外的代碼得到的結果也可能構造出不同的樹。
本題思路是通過有序的序列的中點作為構造的根節(jié)點，以根節(jié)點為中心，將數組一分為二，然后遞歸即可，這里面需要注意左右邊界，我在這里吃了虧，提交了好幾次才過..
代碼如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return sortedArrayToBST(nums,0,nums.length - 1);
}
private TreeNode sortedArrayToBST(int[] nums,int left,int right){
if(left > right){
return null;
}
int rootIndex = left + ((right - left) >> 1);
TreeNode root = new TreeNode(nums[rootIndex]);
root.left = sortedArrayToBST(nums,left,rootIndex - 1);
root.right = sortedArrayToBST(nums,rootIndex + 1,right);
return root;
}
}
時間復雜度：O(N)
額外空間復雜度：重構的二叉樹是我們需要返回的結果，所以這個結果我認為是不算做額外空間的，額外空間實際上只是遞歸棧的深度，因為返回的樹不僅僅是二叉搜索樹也是一棵平衡的樹，所以遞歸棧的深度為O(logN)
執(zhí)行結果：
