- 浏览: 130667 次
文章分类
- 全部博客 (189)
- Tree (14)
- Dynamic Programming (34)
- Array (20)
- Search (1)
- Hash (12)
- Backtracking (22)
- Divide and Conque (8)
- Greedy (6)
- Stack (12)
- software (0)
- List (7)
- Math (22)
- Two pointers (16)
- String (20)
- Linux (1)
- Sliding Window (4)
- Finite State Machine (1)
- Breadth-first Search (7)
- Graph (4)
- DFS (6)
- BFS (3)
- Sort (9)
- 基础概念 (2)
- 沟通表达 (0)
- Heap (2)
- Binary Search (15)
- 小结 (1)
- Bit Manipulation (8)
- Union Find (4)
- Topological Sort (1)
- PriorityQueue (1)
- Design Pattern (1)
- Design (1)
- Iterator (1)
- Queue (1)
最新评论
-
likesky3:
看了数据结构书得知并不是迭代和递归的区别,yb君的写法的效果是 ...
Leetcode - Graph Valid Tree -
likesky3:
迭代和递归的区别吧~
Leetcode - Graph Valid Tree -
qb_2008:
还有一种find写法:int find(int p) { i ...
Leetcode - Graph Valid Tree -
qb_2008:
要看懂这些技巧的代码确实比较困难。我是这么看懂的:1. 明白这 ...
Leetcode - Single Num II -
qb_2008:
public int singleNumber2(int[] ...
Leetcode - Single Num II
[分析]
最近公共祖先(LCA)是一个经典问题,以前没有好好研究过这个问题,不知道还有个Tarjan算法,今天开了眼界。一般有两种方法分别适用不同场景:
1)递归算法,适合在线单次查询,如本题;
2)Tarjan算法,适合批量查询,输入是一颗树和N对定点,为每个顶点(u,v)确定LCA。
有兴趣的同学看参考https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.03.md, July讲得很全面清楚。
抛开算法本身做这道题目还有些学习点:
思路1:分别求出root到p和q的路径,求两条路径从根开始的最后一个公共节点。
实现中getPath2方法暴露没有对回溯掌握得还不够好,回溯时回溯到方法调用前的状态即可,不能多也不能少,这里就属于回溯过头了。
LinkedList被当做stack使用时get(0)获得的是栈顶元素,之前错误的认为调用get(i)就类似操作ArrayList的get(i), 按加入顺序返回。
思路2:经典的递归写法,牢记树的很多问题都可以用递归解决,因为树本身是递归描述的。
最近公共祖先(LCA)是一个经典问题,以前没有好好研究过这个问题,不知道还有个Tarjan算法,今天开了眼界。一般有两种方法分别适用不同场景:
1)递归算法,适合在线单次查询,如本题;
2)Tarjan算法,适合批量查询,输入是一颗树和N对定点,为每个顶点(u,v)确定LCA。
有兴趣的同学看参考https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.03.md, July讲得很全面清楚。
抛开算法本身做这道题目还有些学习点:
思路1:分别求出root到p和q的路径,求两条路径从根开始的最后一个公共节点。
实现中getPath2方法暴露没有对回溯掌握得还不够好,回溯时回溯到方法调用前的状态即可,不能多也不能少,这里就属于回溯过头了。
LinkedList被当做stack使用时get(0)获得的是栈顶元素,之前错误的认为调用get(i)就类似操作ArrayList的get(i), 按加入顺序返回。
思路2:经典的递归写法,牢记树的很多问题都可以用递归解决,因为树本身是递归描述的。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null) return root; else return left != null ? left : right; } public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) { LinkedList<TreeNode> path1 = new LinkedList<TreeNode>(); getPath(root, p, path1); LinkedList<TreeNode> path2 = new LinkedList<TreeNode>(); getPath(root, q, path2); TreeNode lca = root; int i = path1.size() - 1, j = path2.size() - 1; while (i >= 0 && j >= 0) { if (path1.get(i) != path2.get(j)) break; lca = path1.get(i); i--; j--; } return lca; } private boolean getPath(TreeNode root, TreeNode x, LinkedList<TreeNode> path) { if (root == null) return false; path.push(root); if (root == x || getPath(root.left, x, path) || getPath(root.right, x, path)) return true; else{ path.pop(); return false; } } // Wrong version private boolean getPath2(TreeNode root, TreeNode x, LinkedList<TreeNode> path) { if (root == null) return false; path.push(root); if (root == x) { return true; } if (getPath(root.left, x, path)) return true; else { if (!path.isEmpty()) { path.pop(); } if (getPath(root.right, x, path)) return true; else if (!path.isEmpty()) { path.pop(); } } return false; }
发表评论
-
Smallest Rectangle Enclosing Black Pixels
2016-02-13 12:39 864An image is represented by a bi ... -
Inorder Successor in BST
2015-09-26 17:49 688[分析] 参考https://leetcode.com/dis ... -
Leetcode - Closest Binary Search Tree Value II
2015-09-13 14:16 748[分析] 思路1:遍历所有节点找到和 target最接近的 k ... -
Leetcode - Surrounded Regions
2015-09-02 13:41 2655[分析] 思路1:和Number of Islands类似,但 ... -
Leetcode - Number of Islands
2015-09-02 09:40 2896[分析] BFS & DFS法详见实现。 这里阐述下u ... -
Leetcode - Graph Valid Tree
2015-09-02 08:50 2237Given n nodes labeled from 0 to ... -
Leetcode - Closest Binary Search Tree Value II
2015-09-01 09:50 3140Given a non-empty binary search ... -
Leetcode - Binary Tree Upside Down
2015-08-29 18:50 383Given a binary tree where all t ... -
Leetcode - Verify Preorder Sequence in Binary Search Tree
2015-08-29 16:46 2999[分析] 思路1:暴力法,遍历当前待检查数组,找到第一个大于数 ... -
Leetcode - Converted Sorted List to BST
2015-08-23 20:07 325Given a singly linked list wher ... -
Leetcode - Strobogrammatic Number II
2015-08-22 11:34 1560A strobogrammatic number is a n ... -
Leetcode - Kth Smallest Element in BST
2015-08-11 10:26 619[分析] 思路1: 递归中序遍历,返回中序遍历中的第k个数。 ... -
Leetcode - Recover Binary Search Tree
2015-07-02 09:27 493Two elements of a binary search ... -
Leetcode - Validate Binary Search Tree
2015-07-01 08:31 563Given a binary tree, determine ... -
Leetcode - Count Complete Tree Nodes
2015-06-07 20:51 740Definition of a complete binary ... -
Leetcode - Contains Duplicate III
2015-06-07 20:08 472Given an array of integers, fi ... -
MockInterview-FindNextValue
2015-04-12 08:57 0[题目] Return the next elemen ... -
MockInterview-Implement Dictionary
2015-04-12 08:56 0[题目] Implement a dictionary, s ... -
Leetcode - Unique Binary Search Trees
2015-04-10 10:00 537[题目] Given n, how many struc ...
相关推荐
Lowest Common Ancestor of a Binary Search Tree Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. According to the definition of LCA on Wikipedia:...
1123.Lowest_Common_Ancestor_of_Deepest_Leaves最深叶节点的最近公共祖先【LeetCo
Range Minimum Query and Lowest Common Ancestor[翻译]1
Given a rooted binary tree, return the lowest common ancestor of its deepest leaves. Recall that: The node of a binary tree is a leaf if and only if it has no children The depth of the root of ...
lowest common ancestor
This program calculates the lowest common multiple of two numbers using Euclid s algorithm. To do this we will read the two numbers and we do accounts required to calculate
要在控制台中运行特定问题,请转至文件test,将调用添加到测试函数( test() ),然后在控制台node <problem> (例如, node LeetcodeProblems/Lowest_Common_Ancestor_of_a_Binary_Tree.js )。 Leetcode问题 名称...
Binary Lifting for LCA(lowest common ancestor) ---, 5.贪婪 6. Manacher/KMP算法 (未完成) 7. 添加 8. 指针 滑动窗口 9.前缀总和 10.递归/DFS 11.棘手的方法 (未完成) 12. 堆栈 Monotonic_Stack 13. 14. ...
非技术人员(包括传教士/儿童/老年人)的简单圣经免费软件小 1.2 兆下载与 OT+NT。 < 1 秒启动和搜索甚至在过时的最低公分母 486 上(1 GB 高清、640*480 分辨率、16 mb 内存、无 CD、28.8 调制解调器、Win95)
8-1 Students I (10分)Write a program that asks you 10 records of students. Each record consists of a name (w/o space) and scores for three courses (in integer 1 to 5). Output a list as following and ...
It begins with a global introduction, from the high-level view to the lowest common denominator (the chip itself), then moves on to the three main building blocks of an SOC (processor, memory, and ...
On a qualified select, update, or delete, the correct leaf page will be the lowest page of the tree in which one or more rows with the specified key or keys reside. A qualified operation is one that ...
tictax:Web服务的流序列分类 使用One Codex和EBI API从命令行或Python快速便捷地实现最低的祖先(LCA)分配。 以正确的方向吹风,每秒可发出约100个请求。... kmer-lca Lowest common ancestor sequ
The shapes are defined by a binary mask outlining the objects. The evaluation protocol for this retrieval task is the bullseye rating, in which each image is used as reference and compared to all of ...
5.1.2 Lowest Common Ancestor (LCA) 53 5.1.3 Reduction from LCA to RMQ 56 5.1.4 From RMQ to LCA 57 5.1.5 An(N), O(1)> algorithm for the restricted RMQ 60 5.1.6 An AC programme 61 5.2 最长公共子序列LCS ...
针对已有方法不能正确求解基于ELCA(exclusive lowest common ancestor)语义的相关关键字节点(RKN,relevant keyword node)的问题,提出RKN的形式化定义及相应的RKN-Base算法。该算法通过顺序扫描每个关键字节点一次...
5.1.2 Lowest Common Ancestor (LCA) 53 5.1.3 Reduction from LCA to RMQ 56 5.1.4 From RMQ to LCA 57 5.1.5 An(N), O(1)> algorithm for the restricted RMQ 60 5.1.6 An AC programme 61 5.2 最长公共子序列LCS ...
Clearly, there is a need for a deep understanding of the fundamental mechanisms governing the process by which device, substrate, and supply noise turn into jitter and phase noise. Existing models ...
to enable a common design to scale across families for optimal power, performance, and cost. The Spartan®-7 family is the lowest density with the lowest cost entry point into the 7 series portfolio...
Packing problems have been a source of fascination for millennia and their study has produced a rich literature that spans numerous disciplines. Investigations of hard-particle packing models have ...