leetcode树有关题目随笔

2019/11/22

109题 没想到用两个指针 好在可以自己想出点东西 但是是错的错误如下：

/**
 * 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) {
        int len = 1;
        ListNode cur = head;
        while(cur.next!=null){
            len +=1;
            cur=cur.next;
        }
        return sortedListToBST(head,0,len);
    }
    private TreeNode sortedListToBST(ListNode head,int start,int end){
        int mid=(start+end)>>>1;
        ListNode cur = head;
        int i=mid;
        while(i>0){
            cur=cur.next;
            i--;
        }
        TreeNode root = new TreeNode(cur.val);
        root.left=sortedListToBST(head,start,mid-1);
        root.right=sortedListToBST(cur,mid+1,end);
        return root;
    }
}

View Code

注意体会官方解法方法 3：中序遍历模拟用到的思想。

1做过数组还原平衡二叉搜索树（推荐先做题号108），我们知道，在array中每次取中点作为根节点，左右分别构建左右子树，递归直至根节点为空。
2链表的特性导致我们无法像数组那样通过下标访问各个元素。若想按照108题的做法，就需要设置两个指针p1 p2，p1每走一步p2走两步，这样p2结束时p1就在中点。但这样会导致每次递归都需要重复遍历链表，效率较低。
3我们考虑是否可以让建立节点的顺序匹配链表元素顺序？这样每次建立节点时，只需要获取链表下一个元素即可。
4使用递归模拟中序遍历过程，建立节点的顺序即与链表元素顺序一一对应，bottom-up建立树，最终返回根节点。
5递归前需要统计链表长度n，整体算法复杂度O(N)。