leetcode 236. Lowest Common Ancestor of a Binary Tree 最近公告祖先LCA + 二叉树 + 深度优先遍历DFS

╰+哭是因爲堅強的太久メ 2022-06-08 12:45 165阅读 0赞

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

_______3______
       /              \
    ___5__          ___1__
    /      \        /      \
    6      _2       0       8
          /  \
          7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

和上一道题一样，直接DFS深度优先遍历即可。

建议和这道题[leetcode 235. Lowest Common Ancestor of a Binary Search Tree 最近公共祖先 + BST][leetcode 235. Lowest Common Ancestor of a Binary Search Tree _ _ BST] 一起学习。

代码如下：

/*class TreeNode 
    {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode(int x) { val = x; }
    }*/
    
    
    public class Solution 
    {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
        {
            //发现目标节点则通过返回值标记该子树发现了某个目标结点
            if(root == null || root == p || root == q) 
                return root;
    
            //查看左子树中是否有目标结点，没有为null
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            //查看右子树是否有目标节点，没有为null
            TreeNode right = lowestCommonAncestor(root.right, p, q);
    
            //都不为空，说明做右子树都有目标结点，则公共祖先就是本身
            if(left!=null&&right!=null)
                return root;
    
            //如果发现了目标节点，则继续向上标记为该目标节点
            return left == null ? right : left;
        }
    }

下面是C++的做法，这里还是DFS深度优先搜索来遍历二叉树来找到LCA的，值得学习

代码如下：

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <string>
    #include <map>
    
    using namespace std;
    
    
    /*
    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 == NULL || root == p || root == q)
                return root;
            else
            {
                TreeNode* left = lowestCommonAncestor(root->left, p, q);
                TreeNode* right = lowestCommonAncestor(root->right, p, q);
                if (left != NULL && right != NULL)
                    return root;
                else
                    return left != NULL ? left : right;
            }
        }
    };

[leetcode 235. Lowest Common Ancestor of a Binary Search Tree _ _ BST]: http://blog.csdn.net/jackzhang_123/article/details/78091573