Shulou(Shulou.com)06/01 Report--

In order to solve the problem of what is the nearest common ancestor in python binary tree, this article introduces the corresponding analysis and solution in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible way.

Given a binary search tree, find the nearest common ancestor of the two specified nodes in the tree.

The recent common ancestor in Baidu encyclopedia is defined as: "for the two nodes p and Q with root tree T, the nearest common ancestor is expressed as a node x, satisfying that x is the ancestor of p and Q and that x is as deep as possible (a node can also be its own ancestor)."

For example, given the following binary search tree: root = [6, 2, 8, 0, 4, 7, 9, 9, 6, 7, 9, 5]

Example 1:

Input: root = [6, 2, 8, 8, 0, 4, 7, 7, 9, 9, 5], p = 2, Q = 8 output: 6 explanation: the node and its nearest common ancestor are

Example 2:

Input: root = [6, 2, 8, 4, 0, 7, 7, 7, 9, 9, 5], p = 2, Q = 4 output: 2 explanation: the nearest common ancestor of the node and the node is, because by definition the nearest common ancestor node can be the node itself.

Description:

The values of all nodes are unique.

P and Q are different nodes and all exist in the given binary search tree.

Ideas for solving the problem:

1. Use the properties of the binary search tree:

A, if the maximum value of pquotiq is less than the root node, the ancestor is in the left subtree.

B, the minimum is greater than the root node, and the ancestor is in the right subtree.

C, ancestor is the root node

2. Note that the size of pmaeq is uncertain.

/ * Definition for TreeNode. * type TreeNode struct {* Val int * Left * ListNode * Right * ListNode * * / func lowestCommonAncestor (root, p, Q * TreeNode) * TreeNode {if root==nil {return root} if p.Val

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.