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

How to understand the recent common ancestor of binary tree? aiming at this problem, 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.

Topic: given a binary tree, find the nearest common ancestor of two specified nodes in the tree.

Three situations are discussed:

If p and Q are the left and right nodes of root, then root is the nearest common ancestor we are looking for.

If p and Q are both left nodes of root, then return lowestCommonAncestor (root.left,p,q)

If p and Q are both right nodes of root, then return lowestCommonAncestor (root.right,p,q)

Class Solution {

Public TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode Q) {

If (root = = null) return root

If (p = = root | | Q = = root) return root

TreeNode rleft = lowestCommonAncestor (root.left, p, Q)

TreeNode rright = lowestCommonAncestor (root.right, p, Q)

If (rleft = = null) return rright

If (rright = = null) return rleft

Return root; / / now is the p and Q nodes and then the left and right sides of the root node.

}

}

The answer to the question about how the recent public ancestors of the binary tree should understand is shared here. I hope the above content can be of some help to you. If you still have a lot of doubts to be solved, you can follow the industry information channel for more related knowledge.

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.