分享

二叉树

 dinghj 2019-04-22

已知二叉树,求二叉树中给定的两个节点的最近公共祖先。 最近公共祖先: 两节点v与w的最近公共祖先u,满足在树上最低(离根最 远),且v,w两个节点都是u的子孙。
LeetCode 236. Lowest Common Ancestor of a Binary Tree

思考与分析

1.两个节点的公共祖先一定在从根节点,至这两个节点的路径上。
2.由于求公共祖先中的最近公共祖先,那么即同时出现在这两条路
径上的离根节点最远的节点(或离两个最近)。
3.最终算法即:求p节点路径,q节点路径,两路径上最后一个相同 的节点。

从根节点到某节点路径(深度搜索)
1.从根节点遍历(搜索)至该节点,找到该节点后就结束搜索。
2.将遍历过程中遇到的节点按照顺序存储起来,这些节点即路径节点。
前序遍历(深度优先)

  1. void preorder(TreeNode *node, TreeNode *search){
  2. if(!node){
  3. return;
  4. }
  5. if(node == search){
  6. }
  7. preorder(node->left,search);
  8. preorder(node->right,search);
  9. }

求根节点至某节点路径

  1. void preorder(TreeNode *node,TreeNode *search, std::vector<TreeNode*> &path,std::vector<TreeNode*> &result,int &finish)//node 正在遍历节点,search待搜索节点,path 遍历时节点路径栈,result 最终搜索到节点search的路径结果,finish 记录是否找到节点search的遍历,未找到时是0,找到为1{
  2. if(!node || finish){
  3. return;//当node为空或已找到search 节点直接返回,结束搜索
  4. }
  5. path.push_back(node);//先序遍历时,将节点压入path栈
  6. if(node == search){
  7. finish = 1;
  8. result = path;
  9. }
  10. preorder(node->left,search,path,result,finish);
  11. preorder(node->right,search,path,result,finish);
  12. path.pop_back();//结束遍历node时,将node节点弹出path栈
  13. }

1.求出较短路径的长度n。
2.同时遍历p节点的路径与q节点的路径,遍历n个节点,最后一个相同节点,即最近 公共祖先。

  1. class Solution{
  2. public:
  3. TreeNode* lowestCommonAncestor(TreeNode * root, TreeNode *p ,TreeNode *q){
  4. std::vector<TreeNode*> path;申明遍历用的临时栈
  5. std::vector<TreeNode*> node_p_path;//储存P节点路径
  6. std::vector<TreeNode*>node_q_path;//储存q节点路径
  7. int finish = 0;//记录是否完成搜索
  8. preorder(root, p,path,node_p_path,finish);
  9. path.clear();//清空path,finish,计算q节点路径
  10. finish = 0;
  11. preorder(root, q, path,node_q_path,finish);
  12. int path_len = 0;
  13. if(node_p_path.size() < node_q_path.size()){
  14. path_len = node_p_path.size();
  15. }
  16. else{
  17. path_len = node_q_path.size();
  18. }
  19. TreeNode * result = 0;
  20. for (int i = 0; i < path_len; i++){
  21. if(node_p_path[i] = node_q_path[i]){
  22. result = node_p_path[i];
  23. }//最后相同的节点为最近公共节点
  24. }
  25. return result;
  26. }
  27. };

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多