给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
Java solution1
static int BOTH_PENDING = 2;
static int LEFT_DONE = 1;
static int BOTH_DOWN = 0;
public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
Stack<Pair<TreeNode , Integer >> stack = new Stack<>();
stack.push(new Pair<TreeNode, Integer>(root, BOTH_PENDING));
boolean one_node_found = false;
TreeNode LCA = null;
while(!stack.empty()){
Pair<TreeNode, Integer> pair = stack.peek();
TreeNode parentNode = pair.getKey();
int parentState = pair.getValue();
if( parentState != BOTH_DOWN){
TreeNode childNode ;
if( parentState == BOTH_PENDING){
if( parentNode == p || parentNode == q){
if(one_node_found){
return LCA;
}
else{
one_node_found = true;
LCA = stack.peek().getKey();
}
}
childNode = parentNode.left;
}
else{
childNode = parentNode.right;
}
stack.pop();
stack.push(new Pair<TreeNode, Integer>(parentNode, parentState -1 ));
if(childNode != null){
stack.push(new Pair<TreeNode, Integer>(childNode, BOTH_PENDING));
}
}
else{
if(LCA == stack.pop().getKey() && one_node_found){
LCA = stack.peek().getKey();
}
}
}
return LCA;
}
Java Solution2
public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
return root;
}
if(root == p || root == q){
return root;
}
TreeNode left = lowestCommonAncestor2(root.left , p,q);
TreeNode right = lowestCommonAncestor2(root.right, p, q);
if(left !=null && right !=null){
return root;
}
else if(left !=null){
return left;
}
else if(right != null){
return right;
}
return null;
}
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# my solution
# class Solution:
# def dfs(self, root: 'TreeNode', p: 'TreeNode' , stack: list) :
# if( root == None):
# return None
# if(root == p ):
# stack.append(root)
# return True
# ans = False
# if( root.left != None):
# stack.append(root)
# ans = self.dfs(root.left,p, stack)
# if(not ans):
# stack.pop(-1)
# else:
# return ans
# if ( root.right != None):
# stack.append(root)
# ans = self.dfs(root.right,p, stack)
# if(not ans):
# stack.pop(-1)
# else:
# return ans
#
# return ans
#
# def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# p_stack = []
# self.dfs(root, p,p_stack)
# q_stack = []
# self.dfs(root, q,q_stack)
#
# p_stack.reverse()
# q_stack.reverse()
# for i_node in p_stack:
# for j_node in q_stack:
# if( i_node.val == j_node.val ):
# return i_node
# 方法一：递归
# class Solution:
# def __init__(self):
# self.ans = None
#
# def lowestCommonAncestor(self, root, p, q):
# def recurse_tree(current_node):
# if not current_node:
# return False
# left = recurse_tree( current_node.left)
# right = recurse_tree( current_node.right)
# mid = current_node == p or current_node == q
# if( mid + left + right >= 2):
# self.ans = current_node
# return mid or left or right
# recurse_tree(root)
# return self.ans
def pre_order_receverse(root : 'TreeNode'):
stack = []
pNode = root
while( pNode != None or len(stack) > 0 ):
if( pNode != None ):
print(pNode.val)
pNode = pNode.left
else:
node = stack.pop()
stack.append(pNode)
pNode = node.right
def dfs_order_receverse(root : 'TreeNode'):
stack = [root]
# pNode = root
while( len(stack) > 0 ):
pNode = stack.pop(-1)
print(pNode.val)
if( pNode.right != None ):
stack.append(pNode.right)
if( pNode.left != None ):
stack.append(pNode.left)
# 方法二：使用父指针迭代
# class Solution:
# def lowestCommonAncestor(self, root, p, q):
# stack = []
# parent = {}
# parent[root] = None
# stack.append(root)
# while p not in parent or q not in parent:
# node = stack.pop(-1)
# if(node.left ):
# parent[node.left] = node
# stack.append(node.left)
# if(node.right):
# parent[node.right] = node
# stack.append(node.right)
# ancestor = set()
# while(p):
# ancestor.add(p);
# p = parent[p]
# while( q not in ancestor):
# q = parent[q]
# return q
# 方法三 无父指针的迭代
class Solution:
# Three static flags to keep track of post-order traversal.
# Both left and right traversal pending for a node.
# Indicates the nodes children are yet to be traversed.
BOTH_PENDING = 2
# Left traversal done.
LEFT_DONE = 1
# Both left and right traversal done for a node.
# Indicates the node can be popped off the stack.
BOTH_DONE = 0
def lowestCommonAncestor(self, root, p, q):
stack = [(root, Solution.BOTH_PENDING)]
one_node_found = False
LCA_index = -1
while stack:
parent_node, parent_state = stack[-1]
if parent_state != Solution.BOTH_DONE:
if parent_state == Solution.BOTH_PENDING:
if parent_node == p or parent_node == q:
if one_node_found:
return stack[LCA_index][0]
else:
one_node_found = True
LCA_index = len(stack) - 1
child_node = parent_node.left
else:
child_node = parent_node.right
stack.pop()
stack.append((parent_node, parent_state - 1))
if child_node:
stack.append((child_node, Solution.BOTH_PENDING))
else:
if one_node_found and LCA_index == len(stack) - 1:
LCA_index -= 1
stack.pop()
return None
if __name__ == '__main__':
root = TreeNode(3)
node1 = TreeNode(5)
node2 = TreeNode(1)
node3 = TreeNode(6)
node4 = TreeNode(2)
node5 = TreeNode(0)
node6 = TreeNode(8)
node7 = TreeNode(7)
node8 = TreeNode(4)
root.left = node1
root.right = node2
node1.left = node3
node1.right = node4
node2.left = node5
node2.right = node6
node4.left = node7
node4.right = node8
p = node1
q = node2
# dfs_order_receverse(root)
print( Solution().lowestCommonAncestor(root, p, q).val )
Java solution1