In this article, we will take a detailed look at the definition and solutions of the Lowest Common Ancestor (LCA) problem.<\/p>\n<\/header>\n Find the lowest common ancestor of two nodes in a binary tree. The lowest common ancestor is the ancestor of both nodes and is the closest node to both nodes.<\/p>\n For example, given the following binary tree:<\/p>\n The lowest common ancestor of node 5 and node 1 is 3, and the lowest common ancestor of node 5 and node 4 is 5.<\/p>\n To find the lowest common ancestor of two nodes in the given binary tree, two conditions must be satisfied:<\/p>\n To establish this relationship, we can traverse the binary tree while tracking the parent node for each node.<\/p>\n First, to find a specific node in the binary tree, we can use search techniques such as DFS (Depth First Search) or BFS (Breadth First Search).<\/p>\n The specific algorithm to find the lowest common ancestor is as follows:<\/p>\n The key points in the above code are as follows:<\/p>\n The time complexity of this algorithm is O(N), as each node in the collection is visited once. N is the number of nodes in the tree.<\/p>\n The space complexity is O(H), where H is the height of the tree. In the worst case, if the binary tree is skewed to one side, the maximum height can be N.<\/p>\n<\/section>\n To test the problem in practice, let’s create an example tree and write code to find the LCA.<\/p>\n In this article, we covered the problem of finding the lowest common ancestor in a binary tree, explaining the problem definition, algorithm design, Java code implementation, and code testing. This problem can be applied in various situations and is very helpful for understanding the basic concepts of algorithms and data structures.<\/p>\n Through this, you can learn useful algorithm patterns for preparing for coding tests in Java and contribute to improving your problem-solving skills.<\/p>\n<\/section>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"Problem Definition<\/h2>\n
Problem: Lowest Common Ancestor (LCA)<\/h3>\n
\n 3\n \/ \\\n 5 1\n \/ \\ \/ \\\n 6 2 0 8\n \/ \\\n 7 4\n <\/pre>\n
Input Format<\/h4>\n
\n
Output Format<\/h4>\n
\n
Problem Solution<\/h2>\n
1. Problem Analysis<\/h3>\n
\n
2. Algorithm Design<\/h3>\n
\n
3. Java Code Implementation<\/h3>\n
\npublic class TreeNode {\n int val;\n TreeNode left;\n TreeNode right;\n\n TreeNode(int x) {\n val = x;\n }\n}\n\npublic class LCA {\n public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {\n \/\/ Base case\n if (root == null || root == p || root == q) {\n return root;\n }\n\n \/\/ Find LCA in the left and right subtrees.\n TreeNode left = lowestCommonAncestor(root.left, p, q);\n TreeNode right = lowestCommonAncestor(root.right, p, q);\n\n \/\/ If both are found, current node is the LCA.\n if (left != null && right != null) {\n return root;\n }\n\n \/\/ Return the result from the subtree where one was found.\n return left != null ? left : right;\n }\n}\n <\/pre>\n4. Code Explanation<\/h3>\n
\n
5. Time Complexity<\/h3>\n
6. Space Complexity<\/h3>\n
Practical Code Test<\/h2>\n
\npublic class Main {\n public static void main(String[] args) {\n \/\/ Creating the binary tree\n TreeNode root = new TreeNode(3);\n TreeNode node5 = new TreeNode(5);\n TreeNode node1 = new TreeNode(1);\n TreeNode node6 = new TreeNode(6);\n TreeNode node2 = new TreeNode(2);\n TreeNode node0 = new TreeNode(0);\n TreeNode node8 = new TreeNode(8);\n TreeNode node7 = new TreeNode(7);\n TreeNode node4 = new TreeNode(4);\n\n root.left = node5;\n root.right = node1;\n node5.left = node6;\n node5.right = node2;\n node1.left = node0;\n node1.right = node8;\n node2.left = node7;\n node2.right = node4;\n\n \/\/ Create an object to find the LCA\n LCA lcaFinder = new LCA();\n TreeNode lca = lcaFinder.lowestCommonAncestor(root, node5, node1);\n System.out.println(\"LCA of 5 and 1: \" + lca.val); \/\/ Output: 3\n\n lca = lcaFinder.lowestCommonAncestor(root, node5, node4);\n System.out.println(\"LCA of 5 and 4: \" + lca.val); \/\/ Output: 5\n }\n}\n <\/pre>\n<\/section>\nConclusion<\/h2>\n