网站建设价格标签职业技能培训学校

题目

方法一：后序遍历 + 回溯

解题的核心就是：采用后序遍历

1. 讨论p，q是否在当前的root的两边，如在两边则返回当前节点root

2. 如何不在两边，只要出现一个节点等于p或者q就返回当前节点
   

// 后序遍历  + 回溯public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null) return null;//即做节点判空条件、、也做递归出口 （说明递归到null  都没有找到  p或q）if(root == p || root == q)  return root;//  说明（当前要递归的节点就是p或q直接返回）或递归找到了p或q  就不用再往下递归了 结束此次递归  返回 p 或 qTreeNode left = lowestCommonAncestor(root.left,p,q);//递归左子树,返回值就是找到的p或q  没找到就是nullTreeNode right = lowestCommonAncestor(root.right,p,q);//递归右子树返回值就是找到的p或q  没找到就是nullif(left!=null  && right!=null) return root;// 如果遍历左右子树 在左子树或右子树找到了都找到了（  p  或  q  ）//  说明当前结点就是  p  q  的最近公共祖先if(left != null && right == null) return left;//如果当前遍历左右子树结点只找到  一个 （q 或者 p）//说明下一个p或者q其实就是在这个结点下面 因为一旦找到了p 或q就不会往下遍历了，// 所以一旦出现只能找到一个（q  或  p）的情况 说明这个这个节点即是（p 或 q） 又是q 和 p 的最近公共祖先if(right != null && left==null) return right; return null;//所有都不满足直接返回null}

二叉树的最近公共祖先（DFS ，清晰图解）