面试经典150题【61-70】

61.旋转链表

本质是调换这俩

第一步：成环。第二步：找head, 第三步：断环

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null|| k == 0)  return head;
        int n = 0;			   //链表的长度
        ListNode tail = null;  //尾节点
        for(ListNode p = head; p != null ; p = p.next){
            tail = p;
            n++;
        }
        k %= n;
        ListNode p = head;
        for(int i = 0; i < n - k - 1; i++)  p = p.next;   //找到链表的第n-k个节点
        tail.next = head;
        head = p.next;
        p.next = null;
        return head;  //返回新的头节点
    }
}

86.分隔链表

新建两个链表，一个里面的值恒小于x,一个里面的值恒大于等于x，再合并两个链表即可。

class Solution {
    public ListNode partition(ListNode head, int x) {
        // 新建两个链表
        ListNode smlDummy = new ListNode(0), bigDummy = new ListNode(0);
        // 遍历链表
        ListNode sml = smlDummy, big = bigDummy;
        while (head != null) {
            // 将 < x 的节点加入 sml 节点后
            if (head.val < x) {
                sml.next = head;
                sml = sml.next;
            // 将 >= x 的节点加入 big 节点后
            } else {
                big.next = head;
                big = big.next;
            }
            head = head.next;
        }
        // 拼接两链表
        sml.next = bigDummy.next;
        big.next = null;
        return smlDummy.next;
    }
}

104. 二叉树的最大深度

树的问题最经典的就是DFS和BFS。
DFS：

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right)) +1;
    }
}

BFS就是创建一个队列，一行一行遍历。看看能遍历几行罢了。

100.相同的树

树这里就是递归去做就行。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null &&q==null) return true;
        //只有一个为Null ，那肯定不一样
        if(p==null) return false;
        if(q==null) return false;
        //比较值和左右子树
        return p.val==q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);

    }
}

226.翻转二叉树

树这边还是用递归，先处理自己的逻辑，然后直接扔给左右子节点。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        TreeNode temp=root.left;
        root.left=root.right;
        root.right=temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;

    }
}

101.对称二叉树

永远是最左边的和最右边的想比较，然后往里面靠近。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        return compare(root.left, root.right);

    }
    public boolean compare(TreeNode left,TreeNode right){
        if(left==null && right==null) return true;
        if(left ==null && right!=null) return false;
        if(left!=null && right==null) return false;
        if(left.val==right.val){
            boolean b1=compare(left.left,right.right);
            boolean b2=compare(right.left,left.right);
            return b1&&b2;
        }
        return false;
    }
}

105.从前序与中序遍历序列构造二叉树

根据preorder[0]去切开Inorder数组，并且得知数量后，再行切开preorder数组，最后迭代即可。

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0) return null;
        TreeNode root=new TreeNode(preorder[0]);
        int i=0;
        for(int j=0;j<inorder.length;j++){
            if(inorder[j]==preorder[0]) i=j;
        }
        int[] inorder1=Arrays.copyOfRange(inorder,0,i);
        int[] inorder2=Arrays.copyOfRange(inorder,i+1,inorder.length);
        int[] preorder1=Arrays.copyOfRange(preorder,1,1+i);
        int[] preorder2=Arrays.copyOfRange(preorder,1+i,preorder.length);
        root.left=buildTree(preorder1,inorder1);
        root.right=buildTree(preorder2,inorder2);
        return root;

    }
}

106.从后序和中序遍历序列构造二叉树

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder.length == 0) return null;
        TreeNode root=new TreeNode(postorder[postorder.length-1]);
        int i=0;
        for(int j=0;j<inorder.length;j++){
            if(inorder[j]==postorder[postorder.length-1]) i=j;
        }
        int[] inorder1=Arrays.copyOfRange(inorder,0,i);
        int[] inorder2=Arrays.copyOfRange(inorder,i+1,inorder.length);
        int[] postorder1=Arrays.copyOfRange(postorder,0,i);
        int[] postorder2=Arrays.copyOfRange(postorder,i,postorder.length-1);
        root.left=buildTree(inorder1,postorder1);
        root.right=buildTree(inorder2,postorder2);
        return root;

    }
}

117.填充每个节点的下一个右侧节点指针II

用个BFS就行了

class Solution {
     public Node connect(Node root){
         if(root==null) return null;
        LinkedList<Node> queue=new LinkedList<>();
        queue.addLast(root);
        while(!queue.isEmpty()){
            Node temp=null;
            Node pre=null;
            int queueSize= queue.size();
            for(int i=0;i<queueSize;i++){
                temp=queue.pollFirst();
                if(pre !=null) pre.next=temp;
                pre =temp;
                if(temp.left!=null) queue.addLast(temp.left);
                if(temp.right!=null) queue.addLast(temp.right);
                
            }
            temp.next=null;
            
        }
        return root;
    }
}

114.二叉树展开为链表

直接先序遍历放到数组里，然后挨个取出来建立新树即可。

class Solution {
 public void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        preorderTraversal(root, list);
        int size = list.size();
        for (int i = 1; i < size; i++) {
            TreeNode prev = list.get(i - 1), curr = list.get(i);
            prev.left = null;
            prev.right = curr;
        }
    }

    public void preorderTraversal(TreeNode root, List<TreeNode> list) {
        if (root != null) {
            list.add(root);
            preorderTraversal(root.left, list);
            preorderTraversal(root.right, list);
        }
    }
}