博客
关于我
牛客网算法——名企高频面试题143题(11)
阅读量:393 次
发布时间:2019-03-04

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

你可能感兴趣的文章
mysql 取表中分组之后最新一条数据 分组最新数据 分组取最新数据 分组数据 获取每个分类的最新数据
查看>>
MySQL 命令和内置函数
查看>>
mysql 四种存储引擎
查看>>
MySQL 在并发场景下的问题及解决思路
查看>>
MySQL 基础架构
查看>>
MySQL 基础模块的面试题总结
查看>>
MySQL 备份 Xtrabackup
查看>>
mYSQL 外键约束
查看>>
mysql 多个表关联查询查询时间长的问题
查看>>
mySQL 多个表求多个count
查看>>
mysql 多字段删除重复数据,保留最小id数据
查看>>
MySQL 多表联合查询:UNION 和 JOIN 分析
查看>>
MySQL 大数据量快速插入方法和语句优化
查看>>
mysql 如何给SQL添加索引
查看>>
mysql 字段区分大小写
查看>>
mysql 字段合并问题(group_concat)
查看>>
mysql 字段类型类型
查看>>
MySQL 字符串截取函数,字段截取,字符串截取
查看>>
MySQL 存储引擎
查看>>
mysql 存储过程 注入_mysql 视图 事务 存储过程 SQL注入
查看>>