建筑网站源码,营销策划方案的主要内容有哪些,中国空间站完成图,什么企业需要网络营销和网络推广文章目录 题目方法一#xff1a;后序遍历 回溯 题目 方法一#xff1a;后序遍历 回溯
解题的核心就是#xff1a;采用后序遍历
讨论p#xff0c;q是否在当前的root的两边#xff0c;如在两边则返回当前节点root 如何不在两边#xff0c;只要出现一个节点等于p或者q就… 文章目录 题目方法一后序遍历 回溯 题目 方法一后序遍历 回溯
解题的核心就是采用后序遍历
讨论pq是否在当前的root的两边如在两边则返回当前节点root 如何不在两边只要出现一个节点等于p或者q就返回当前节点
// 后序遍历 回溯public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root null) return null;//即做节点判空条件、、也做递归出口 说明递归到null 都没有找到 p或qif(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 leftnull) return right; return null;//所有都不满足直接返回null}二叉树的最近公共祖先DFS 清晰图解
