How to understand the nearest common ancestor of binary tree
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.
