从中序和后序遍历序列构造二叉树
题目：根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/
9 20
/
15 7
思路：这个算是上一个题目前序中序构造二叉树的姊妹版，不说一模一样大体思路也是差不多的。只不过前序的第一个是根节点变成了后序的最后一个是根节点。我去尝试写代码了。
第一版代码直接写出来了，就是昨天我自己方法的改版，果然还是自己想的印象深刻。我直接贴代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length==0) return null;
TreeNode res = new TreeNode(postorder[postorder.length-1]);
int i = 0;
while(postorder[postorder.length-1]!=inorder[i]) i++;
res.left = buildTree(Arrays.copyOfRange(inorder,0,i),Arrays.copyOfRange(postorder,0,i));
res.right = buildTree(Arrays.copyOfRange(inorder,i+1,inorder.length),Arrays.copyOfRange(postorder,i,postorder.length-1));
return res;
}
}
额，和昨天一样，实现是ok 的，但是性能很一言难尽，直接附上性能排行第一的代码瞻仰：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
swap(postorder);swap(inorder);
return helper(postorder,inorder,0,postorder.length-1,0,inorder.length-1);
}
public TreeNode helper(int[] pre,int[] in,int pre_left,int pre_right,int in_left,int in_right){
if(pre_left>pre_right) return null;
TreeNode root = new TreeNode(pre[pre_left]);
int i=0;
while(in[i+in_left]!=pre[pre_left]){
i++;
}
TreeNode left_node=helper(pre,in,pre_left+1,pre_left+i,in_left,in_left+i);
TreeNode right_node=helper(pre,in,pre_left+i+1,pre_right,in_left+i+1,in_right);
root.right=left_node;
root.left=right_node;
return root;
}
public void swap(int[] a){
int left=0;int right=a.length-1;
while(left < right){
int temp=a[left];
a[left]=a[right];
a[right]=temp;
left++;right--;
}
}
}
有序链表转化成二叉搜索树
题目：给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/
-3 9
/ /
-10 5
思路：这道题我觉得有点意思啊，怎么说呢，什么都不考虑的情况下应该还是很简单的吧，我不知道坑在哪里，目前的思路就是快慢指针找到链表的中间值，然后作为根节点，然后左右递归，依旧是中间节点作为根节点，就这么一直递归下去。额，还有一点，就是我总觉得链表是很麻烦的东西啊，打算先遍历成数组处理，我去实现下看看。
喏，很佩服我自己，举一反三，完美的用了和上个题类似的方法做出来了，撒花·~~~~我贴代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
List<Integer> list = new ArrayList<Integer>();
while(head!=null){
list.add(head.val);
head = head.next;
}
int[] d = new int[list.size()];
int idx = 0;
for(int i : list){
d[idx] = i;
idx++;
}
return dfs(d);
}
public TreeNode dfs(int[] d){
if(d.length==0) return null;
int i = d.length/2;
TreeNode res = new TreeNode(d[i]);
res.left = dfs(Arrays.copyOfRange(d,0,i));
res.right = dfs(Arrays.copyOfRange(d,i+1,d.length));
return res;
}
}
啊哈，这个是第一版本，其实是有点问题的，这里绝对用不到数组复制，我就是懒得改动所以直接用了。我去改动下：
class Solution {
public TreeNode sortedListToBST(ListNode head) {
List<Integer> list = new ArrayList<Integer>();
while(head!=null){
list.add(head.val);
head = head.next;
}
int[] d = new int[list.size()];
int idx = 0;
for(int i : list){
d[idx] = i;
idx++;
}
return dfs(d,0,d.length);
}
public TreeNode dfs(int[] d ,int start,int end){
if(start>=end) return null;
int i = (end+start)/2;
TreeNode res = new TreeNode(d[i]);
res.left = dfs(d,start,i);
res.right = dfs(d,i+1,end);
return res;
}
}
额，不用数组来回来去复制了，但是性能还没上来。。我去瞻仰性能排行第一的代码了，唔，跟我第一个想法一样，快慢指针找中点，然后来回来去的，我直接贴代码：
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
ListNode dummyNode = new ListNode(1);
dummyNode.next = head;
ListNode f = head;
ListNode s = dummyNode;
while (f.next != null && f.next.next != null) {
f = f.next.next;
s = s.next;
}
TreeNode nh = new TreeNode(s.next.val);
nh.right = sortedListToBST(s.next.next);
s.next = null;
nh.left = sortedListToBST(dummyNode.next);
return nh;
}
}
说实话这个方法我想到了，不过我以为来回来去链表遍历会比这个数组浪费性能呢，所以pass了。。哈哈，看来还是我理解的不够深刻哈。。这道题就这么过了。
路径总和2
题目：给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/
4 8
/ /
11 13 4
/ \ /
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
思路：这个题怎么说呢，标准回溯？做法肯定是从根节点开始，选择当前元素，把所有能向下走的路径记录，然后最后到了叶子节点，是给定值则添加到结果集，不是给定值则这条路不行，pass。额，至于说到剪枝，我不知道二叉树元素会不会是负数，如果不是的话当当前和大于给定值则可以直接剪枝，但是没这个要求，所以还是先都走一遍吧，我去写下代码。
好吧，挺简单的一道题让我想复杂了，这个题其实就是个遍历的问题，从根节点遍历，到了叶子节点判断和是不是给定值，不是不操作，是则添加res。最后遍历完结果也出来了，我直接贴代码：
/**
* 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>> res;
public List<List<Integer>> pathSum(TreeNode root, int sum) {
res = new ArrayList<List<Integer>>() ;
dfs(new ArrayList<Integer>(),sum,0,root);
return res;
}
public void dfs(List<Integer> list,int sum, int temp,TreeNode root){
if(root==null) return;
temp += root.val;
list.add(root.val);
//到了叶子节点。
if(root.left==null && root.right==null){
if(temp==sum) res.add(list);
}else{
dfs(new ArrayList(list),sum,temp,root.left);
dfs(new ArrayList(list),sum,temp,root.right);
}
}
}
但是这个性能只有3ms，我直接看看大佬的代码吧：
class Solution {
private List<List<Integer>> lists=new ArrayList();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
ArrayList list=new ArrayList();
if(root==null) return lists;
sums(root,sum,list);
return lists;
}
public void sums(TreeNode root, int sum, ArrayList list){
if(root.left==null&&root.right==null&&sum-root.val==0) {list.add(root.val);lists.add(new ArrayList(list));list.remove(list.size()-1);return;}
if(root.left==null&&root.right==null&&sum-root.val!=0) {return;}
list.add(root.val);
if(root.left!=null) sums(root.left, sum-root.val, list);
if(root.right!=null) sums(root.right, sum-root.val, list);
list.remove(list.size()-1);
}
}
说实话，人家的代码性能1ms，挺好的。但是我仍然没有焕然一新的感觉。首先这是标准回溯，回溯三部曲添加，递归，删除一步没少。而我用的新list来解决这个问题，不得不说这么处理更优雅。减少了内存空间的占用。。总体来说是人能想到的，处理的比较优雅的。还不错。
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！生活平平安安健健康康！另外周末愉快~！
网友评论