Razertory 的技术博客

输入一个二叉树的 root 节点，判断是否是二叉搜索树。 1public boolean isBST(TreeNode root) 二叉搜索树的定义： 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 任意节点的左、右子树也分别为二叉查找树； 没有键值相等的节点。 根据这个定义，比如有个函数 f(... 続きを読む…

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前) 1public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) 维护一个二维数组，... 続きを読む…

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 1boolean VerifySquenceOfBST(int [] sequence) BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，... 続きを読む…

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） 1boolean HasSubtree(TreeNode root1,TreeNode root2) 首先在 A 中找到一个节点，满足这个节点是 B 的 root 节点，在此基础上按照 B 的结构遍历 A，B。 12345678910111213141516171819202122boolean H... 続きを読む…

Given a linked list, swap every two adjacent nodes and return its head.You may not modify the values in the list’s nodes, only nodes itself may be changed. 1ListNode swapPairs(ListNode head) 由于要交换... 続きを読む…

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and retur... 続きを読む…

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5 传送门 定义一个 dummy 节点，pre，cur 节点。比较 pre.next 和 cur。如果相同让 pre = pre.next 做删除操作 12345678910... 続きを読む…

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。 传送门 定义一个慢和一个快指针，当两个指针相遇的时候。快指针速度和慢指针一致，等再次相遇的时候这个点就是环入口。 1234567891011121314151617ListNode EntryNodeOfLoop(ListNode pHead) { if (pHead == null || pHea... 続きを読む…

输入两个链表，找出它们的第一个公共结点。 传送门 首先计算出两个链表的各自长度，然后计算出一个差值 delta。然后基于 delta 的值走对应的节点，当 delta 变为 0 的时候停止。并判断是否有公共节点 12345678910111213141516171819202122232425ListNode FindFirstCommonNode(ListNode pHead1, Lis... 続きを読む…

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的 head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空） 传送门 每个链表都有两个指针，这种情况下最简单的做法是用一个 k, v 的方式存放所有的节点以及新的只有 label，指针指向的节点为空的节点。然后用原来的节点指针指向的值复... 続きを読む…