城志

分类

题解(21)

/ 注册

全部文章（共14篇）

判断二叉树是否对称

递归 1. 分析不对称的条件：结点X的左右子树不对称，包括左右子树某一个为null，左右孩子的val不同，左孩子的左子树与右孩子的右子树不对称等等递归的base case是假设知道左右两个子树是否为null、根以及左右子树是否对称。 2. 代码 public class Solution { ...

剑指offer java 二叉树

2020-02-23

0 906

二叉树的最大二叉搜索子树

【典型】树的动态规划问题 1. 分析树形动态规划问题的前提：如果题目要求的目标是规则S，则流程一般是完成每个结点为root时的子树，在规则S下的每一个答案，最终答案一定在这些答案中。本题中，规则是整棵树的最大搜索二叉树（maxBST）。求出每一个节点作为root的子树的maxBST，最终答案...

左程云 java 二叉树 leetcode

2020-02-22

0 1666

验证平衡二叉树

树形动态规划 1.套路 1.1 可能性分析如果root的左子树不是平衡二叉树，则root不是。如果root的右子树不是，则root不是。如果root的左右子树的高度差超过1，则root不是。如果以上三种没出现，那么root是平衡的。 1.2 建立数据结构根据可能性分析列出每个结点所需信...

java 二叉树 leetcode

2020-02-22

0 1153

二叉树某结点在中序遍历的下一个结点

1. 分情况列举 1.1 分析有右孩，返回右子树的中序最左结点无右孩,且它是父亲的左孩，则返回其父无右孩，且它是其父亲的右孩，则从它父亲开始往上找, 直到某个结点，它是其父亲的左孩，返回其父亲。 1.2 代码 /* public class TreeLinkNode { int v...

剑指offer java 二叉树

2020-02-21

0 959

根据先序和中序遍历重建二叉树

1. 递归 1.1 分析 pre[0]是root,在in中找到root的位置找到root位置后，根据其index确定左右子树的pre和in的范围, 递归图片转载自 https://blog.nowcoder.net/n/7131c90ce3214472887b0f2f6652f5a7 注意，Ar...

剑指offer java 二叉树

2020-02-21

0 942

按之字形打印二叉树

1. 双端队列+层次遍历 1.1 分析之字形，要求奇偶层输出顺序相反。双端队列基于LinkedList实现。奇数层，队头出对，孩子从队尾入队，先左后右。偶数层，队尾出队，孩子从队头入队，先右后左。 1.2 代码 import java.util.ArrayList; import java....

左程云 java 二叉树

2020-02-20

0 932

二叉树层次遍历，按层输出

1. 标记每层最右结点 1.1 分析辅助队列last记录本层最右结点，nLast记录下层最右结点（入队时标记）。出队到last时本层输出完，last更新为nLast。 1.2 代码 import java.util.* public class Solution { ArrayList&l...

左程云 java 二叉树

2020-02-20

0 1493

非递归遍历二叉树

import java.util.Stack; class Node{ Node left; Node right; char val; public void Node(char value){ this.val = value; } } ...

左程云 java 二叉树

2020-02-20

0 1055

两链表是否有环+是否相交

1. 分析来源：《程序员代码面试指南》(第2版)左程云单链表是否有环如果一个有环，一个没有，则肯定不想交如果都没有环，找到相交点，参考如果都有环，分三种情况：情况一，环入口一致，相交点在入口前面情况二，环入口不一致，且loop1 loop2在环中不连通，则不相...

左程云 java 链表

2020-02-19

0 1010

合并有序链表

1. 先处理头结点 1.1 分析把两个链表中较小的头作为新链表的头依次比较两个链表未合并部分的头，较小者插入新表的尾处理未走到尽头的链表1.2 代码 public class Solution { public ListNode mergeTwoLists(ListNode l1, Li...

java 链表 leetcode

2020-02-19

39 1435