本文共 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/