本文共 3524 字，大约阅读时间需要 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);    }}

转载地址：http://emch.baihongyu.com/