二叉树最近公共祖先解法全解析

LeetCode236给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”示例输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4输出5解释节点5和节点4的最近公共祖先是节点5 。因为根据定义最近公共祖先节点可以为节点本身。Python解法1.递归# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val x # self.left None # self.right None class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: if not root or root p or root q: return root left self.lowestCommonAncestor(root.left, p, q) right self.lowestCommonAncestor(root.right, p, q) if left and right: return root return left if left else right2.标记DFS# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val x # self.left None # self.right None class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: father dict() visited set() father[root] None def dfs(cur): if cur.left: father[cur.left] cur dfs(cur.left) if cur.right: father[cur.right] cur dfs(cur.right) dfs(root) ptr p while ptr: visited.add(ptr) ptr father[ptr] ptr q while ptr: if ptr in visited: return ptr ptr father[ptr] return NoneJava解法1.递归/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val x; } * } */ 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; } }2.标记DFS/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val x; } * } */ class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 用节点对象做key不依赖val HashMapTreeNode, TreeNode father new HashMap(); HashMapTreeNode, Boolean visited new HashMap(); father.put(root, null); dfs(root, father); // p向上标记 TreeNode ptr p; while (ptr ! null) { visited.put(ptr, true); ptr father.get(ptr); } // q向上查找 ptr q; while (ptr ! null) { if (visited.containsKey(ptr)) return ptr; ptr father.get(ptr); } return null; } private void dfs(TreeNode cur, HashMapTreeNode, TreeNode father) { if (cur.left ! null) { father.put(cur.left, cur); dfs(cur.left, father); } if (cur.right ! null) { father.put(cur.right, cur); dfs(cur.right, father); } } }C解法1.递归/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root nullptr || root p || root q){ return root; } TreeNode* left lowestCommonAncestor(root-left, p, q); TreeNode* right lowestCommonAncestor(root-right, p, q); if(left ! nullptr right ! nullptr)return root; return left ? left : right; } };2.标记DFS/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { unordered_mapTreeNode*, TreeNode* father; unordered_mapTreeNode*, bool visited; // DFS 记录父节点根父节点直接赋值 auto dfs [](auto self, TreeNode* cur) - void { if (!cur) return; if (cur-left) { father[cur-left] cur; self(self, cur-left); } if (cur-right) { father[cur-right] cur; self(self, cur-right); } }; father[root] nullptr; dfs(dfs, root); // p向上标记路径 TreeNode* ptr p; while (ptr) { visited[ptr] true; ptr father[ptr]; } // q向上查找首个访问节点 ptr q; while (ptr) { if (visited[ptr]) return ptr; ptr father[ptr]; } return nullptr; } };