LeetCode Lowest Common Ancestor of a Binary Tree

LeetCode Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.


给定一棵二叉树和两个节点p,q,问p和q的最近公共祖先节点是哪个。LCA问题

思路:要找p和q的最近公共祖先,很直观的方法是找到从根节点分别到p和q的路径,然后把其中一条路径(比如根到p)上的点hash成path1,从另一条路径(比如根到q)的底端(q)往根节点走,把走过的每个点去path1中找,如果找到,则就是他们的LCA,因为这是距离q最近、且在path1中的点。

但是怎样找到根到p和q的路径呢。这里换一种思路,定义如下新的数据结构,par表示该节点的父节点,根节点的父节点为-1。

struct MyNode {
	TreeNode* node;
	int par;
	MyNode(TreeNode* n_, int p_) :node(n_), par(p_) {};
};

先整体把树层次遍历一遍,成为一个保存MyNode的数组,记录每个点的父节点在数组中的下标。在遍历的同时,记录下p和q节点的下标。这样通过下标往前递归就可以找到p和q到根节点的路径了。

找到路径之后,对其中一条路径hash,另一条路径在该hash中找。代码如下:

class Solution {
private:
	struct MyNode {
		TreeNode* node;
		int par;
		MyNode(TreeNode* n_, int p_) :node(n_), par(p_) {};
	};
public:
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		vector<MyNode> nodes;
		int i = 0, j = 0;
		queue<MyNode> tree;
		tree.push({ root,-1 });
		while (!tree.empty()) {
			MyNode cur = tree.front();
			tree.pop();
			if (cur.node == NULL) continue;
			if (cur.node == p)i = nodes.size();
			if (cur.node == q)j = nodes.size();
			tree.push({ cur.node->left,nodes.size() });
			tree.push({ cur.node->right,nodes.size() });
			nodes.push_back(cur);
		}

		if (i == j)return nodes[i].node;

		unordered_set<int> path1;
		while (i != -1) {
			path1.insert(i);
			i = nodes[i].par;
		}

		while (j != -1) {
			if (path1.find(j) != path1.end()) {
				return nodes[j].node;
			}
			j = nodes[j].par;
		}
		return NULL;
	}
};

本代码提交AC,用时19MS。

讨论区还有一种递归的解法,很有意思。我们在以root为根的树中找p和q的LCA,如果root等于p或q其中之一,说明p或q就是他们的LCA。否则分别在左子树和右子树中递归的找LCA,如果发现在左右子树中找到的LCA都不为null,说明他们p和q分别位于root的两个子树,类似样例中的5和1,则root就是他们的LCA。如果某个子树返回的LCA为空,说明p和q都不在这个子树中,则先遇到谁,谁就是LCA,比如样例中的5和4,都不在3的右子树,在递归3的左子树的时候,先遇到了5,所以5是LCA。

完整代码如下:

class Solution {
public:
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		if (root == NULL || root == p || root == q)return root;
		TreeNode* left = lowestCommonAncestor(root->left, p, q);
		TreeNode* right = lowestCommonAncestor(root->right, p, q);
		if (left != NULL&&right != NULL)return root;
		return left != NULL ? left : right;
	}
};

本代码提交AC,用时23MS。

Leave a Reply

Your email address will not be published. Required fields are marked *