049二叉树的最近公共祖先

二叉树的最近公共祖先题目链接https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { StringBuilder pSb new StringBuilder(); StringBuilder qSb new StringBuilder(); //获取pSb dfs(root, p, pSb); //获取qSb dfs(root, q, qSb); //遍历pSb与qSb相同的部分 TreeNode cur root; int i 0, len Math.min(pSb.length(), qSb.length()); while(i len pSb.charAt(i) qSb.charAt(i)){ cur pSb.charAt(i) 0 ? cur.left : cur.right; i; } return cur; } public boolean dfs(TreeNode cur, TreeNode target, StringBuilder sb){ if(cur null){ return false; } if(cur target){ return true; } sb.append(0); boolean flag dfs(cur.left, target, sb); if(flag){ return flag; } sb.deleteCharAt(sb.length()-1); sb.append(1); flag dfs(cur.right, target, sb); if(flag){ return flag; } sb.deleteCharAt(sb.length()-1); return flag; }分析代码的时间复杂度为O(n)空间复杂度为O(n)。解题思路用StringBuilder记录两个节点的路径向左走为0向右走为1。遍历两个节点相同的路径部分得到的节点就是二者的最近公共祖先。看了官方题解后的解答//方法一递归 //时间复杂度O(n) //空间复杂度O(n) public TreeNode ans null; public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { dfs(root, p, q); return ans; } public boolean dfs(TreeNode cur, TreeNode p, TreeNode q){ if(cur null){ return false; } boolean left dfs(cur.left, p, q);//左子树是否存在p节点或q节点 boolean right dfs(cur.right, p, q);//右子树是否存在p节点或q节点 //左右子树分别存在p、q的其中一个或者当前节点就是p或q且当前节点的左子树或右子树存在q或p if((left right) || (cur.val p.val || cur.val q.val) (left || right)){ ans cur; } //当前节点为根节点的子树是否存在p或q return left || right || cur.val p.val || cur.val q.val; } //方法二存储父节点 //时间复杂度O(n) //空间复杂度O(n) public MapInteger, TreeNode parent new HashMap();//key当前节点 value当前节点的父节点 public SetInteger visited new HashSet();//存储从p往上跳已经访问过的节点 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { parent.put(root.val, null); dfs(root); TreeNode node p; while(node ! null){ visited.add(node.val); node parent.get(node.val); } node q; while(node ! null){ if(visited.contains(node.val)){ return node; } node parent.get(node.val); } return null; } public void dfs(TreeNode cur){ if(cur.left ! null){ parent.put(cur.left.val, cur); dfs(cur.left); } if(cur.right ! null){ parent.put(cur.right.val, cur); dfs(cur.right); } }分析​ 1、方法一的解题思路递归到叶子节点从叶子节点往根节点判断是否为最近公共祖先。判断方法判断当前节点的左、右子树是否分别包含p、q的其中一个或者当前节点是否就是p或q节点且当前节点的左子树或右子树同时包含q或p若是则该节点就是p、q的最近公共祖先。​ 2、方法二的解题思路利用哈希表存储每个节点的父节点从p节点往根节点遍历并用visited记录遍历到的节点最后从q节点往根节点遍历遇到的第一个遍历过的节点就是二者的最近公共祖先。总结本题有两种解法一种是通过p、q在当前节点作为根节点的子树上的分布情况来判断另一种是通过记录遍历路径来判断。