城志

题解

/ 注册

全部文章 / 题解（共6篇）

判断二叉树是否对称

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

剑指offer java 二叉树

2020-02-23

0 906

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

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

剑指offer java 二叉树

2020-02-21

0 960

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

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 分析先利用快慢指针判断是否有环，如果有，两者会在环中相遇。再利用同速双指针，分别从相遇点和链表头出发，两者一定在环入口相遇。证明：快指针的路程：s1 = a + k1(b+c) + b慢指针的路程：s2 = a + k2(b+c) + b , 令k2 -...

剑指offer java 链表

2020-02-18

0 866

删除链表中重复的结点

1. 辅助空间 1.1 分析两次遍历链表。第一次遍历，将重复的值存入set。第二次遍历，如果set中存在，则在链表中删除。 1.2 代码 import java.util.HashSet; public class Solution { public ListNode deleteDupl...

剑指offer java 链表

2020-02-18

0 658

从尾到头打印链表

1. 递归 1.1 分析递归的关键，先向下递归再执行本次操作，这样才会形成反序操作序列。递归结束时没有操作，结束的上一步中的操作是反序操作的第一步，在本题中就是list.add(tail.val)。 1.2 代码 import java.util.*; public class Solution ...

剑指offer java 链表

2020-02-16

0 895