牛客网算法——名企高频面试题143题（11）

题目描述

给定一个二叉树，请计算节点值之和最大的路径的节点值之和是多少。 这个路径的开始节点和结束节点可以是二叉树中的任意节点

package 复现代码;
/**
 * @Classname 二叉树的路径和
 * @Description TODO
 * @Date 2020/12/19 15:23
 * @Created by xjl
 */
public class 二叉树的路径和 {
    int res = Integer.MIN_VALUE;

    public int TreeMax(TreeNode root) {
        if (root == null) {
            return 0;
        }
        getMax(root);
        return res;
    }

    private int getMax(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int L = Math.max(0, getMax(root.left));
        int R = Math.max(0, getMax(root.right));
        res = Math.max(res, Math.max(root.val + Math.max(L, R), root.val + R + L));
        return Math.max(L, R) + root.val;
    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }
}

二叉树的直径

package 复现代码;
/**
 * @Classname 二叉树的直径II
 * @Description TODO
 * @Date 2020/12/19 15:35
 * @Created by xjl
 */
public class 二叉树的直径II {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    int maxD = 1;

    public int MaxD(TreeNode root) {
        if (root == null) {
            return 0;
        }
        getD(root);
        return maxD-1;
    }

    private int getD(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int L = getD(root.left);
        int R = getD(root.right);
        maxD = Math.max(maxD, L + R + 1);
        return Math.max(L, R) + 1;
    }
}

题目描述

将给定的单链表 L\ L L： L0→L1→…→Ln−1→LnL_0→L_1→…→L_{n-1}→L_ nL0​→L1​→…→Ln−1​→Ln​ 重新排序为：L0→Ln→L1→Ln−1→L2→Ln−2→…L_0→L_n →L_1→L_{n-1}→L_2→L_{n-2}→…L0​→Ln​→L1​→Ln−1​→L2​→Ln−2​→… 要求使用原地算法，不能改变节点内部的值，需要对实际的节点进行交换。 例如： 对于给定的单链表{10,20,30,40}，将其重新排序为{10,40,20,30}.

package 名企高频面试题143;

import org.junit.Test;

/**
 * @Classname 链表的排序
 * @Description TODO
 * @Date 2020/12/19 15:53
 * @Created by xjl
 */
public class 链表的排序 {

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public void reorderList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null) {
            return ;
        }
        //快慢指针，找到中间节点
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow;
        ListNode start = head;
        ListNode end1 = mid.next;
        //断链
        mid.next = null;
        //链表二进行翻转
        ListNode end = reverList(end1);
        //插入
        while(start != null && end!=null){
            ListNode next1 = start.next;
            ListNode next2 = end.next;
            start.next = end;
            end.next = next1;
            start = next1;
            end = next2;
        }
        return ;
    }

    private ListNode reverList(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

    @Test
    public void test() {
        ListNode root = new ListNode(1);
        ListNode s1 = new ListNode(2);
        ListNode s2 = new ListNode(3);
        ListNode s3 = new ListNode(4);
//        ListNode s4 = new ListNode(5);

        root.next = s1;
        s1.next = s2;
        s2.next = s3;
//        s3.next = s4;

        reorderList(root);
    }
}