二叉樹的層次遍歷Ⅱ
思路：queue
本題和二叉樹的層序遍歷一模一樣，只不過需要返回其節(jié)點值自底向上的層次遍歷結(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í)行結(jié)果：
將有序數(shù)組轉(zhuǎn)換為二叉搜索樹
思路：recursion
如果輸入的序列是有序的序列在跳，我們自然而言就可以聯(lián)想到二叉搜索樹的中序遍歷結(jié)果就是由小到大排列的凿傅。
那么萌京，首先我們思考一個問題：重構(gòu)的二叉搜索樹是唯一的嗎泊交？
答案必然是否定的乳讥，因為我們可以間接認為，給定了有序的輸入序列廓俭，實際上就是給定了二叉搜索樹的中序遍歷的結(jié)果云石，如果只知道中序遍歷的結(jié)果是無法準確確定一個唯一的樹的。如果給定了前序遍歷+中序遍歷的結(jié)果或者是中序遍歷+后續(xù)遍歷的結(jié)果則可以確定一棵唯一的二叉樹研乒，可以參考題目：leetcode105.從前序與中序遍歷序列構(gòu)造二叉樹,106.從中序與后序遍歷序列構(gòu)造二叉樹
所以汹忠，本題的構(gòu)建方法必然不是唯一的，這里只給出了遞歸的求解方式，另外的代碼得到的結(jié)果也可能構(gòu)造出不同的樹宽菜。
本題思路是通過有序的序列的中點作為構(gòu)造的根節(jié)點谣膳，以根節(jié)點為中心，將數(shù)組一分為二铅乡，然后遞歸即可继谚，這里面需要注意左右邊界，我在這里吃了虧阵幸，提交了好幾次才過..
代碼如下：
/**
* 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)
額外空間復雜度：重構(gòu)的二叉樹是我們需要返回的結(jié)果花履，所以這個結(jié)果我認為是不算做額外空間的，額外空間實際上只是遞歸棧的深度挚赊，因為返回的樹不僅僅是二叉搜索樹也是一棵平衡的樹诡壁，所以遞歸棧的深度為O(logN)
執(zhí)行結(jié)果：
