leetcode 1123. 最深叶节点的最近公共祖先【dfs】

悠悠 2022-11-17 14:59 97阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]

图片来自leetcode，侵权请联系删除

[题解参考][Link 1]

如图，我们需要找一个节点，这个节点之下的子树能覆盖所有的最后一层的叶子  
首先就是想到，如果最后一层叶子都在根的左边，那么我们就要在左边找  
如果两边都有的话，直接就是根节。  
可以通过判断左右子树的高度来进行判断

**调用堆栈分析**  
如图，在判断树的高度的时候，使用深度优先搜索  
当搜索到6 7 4 0 8的时候，发现左右子树高度都是零，符合要求  
递归依次向上，7 4 的父亲节点2满足， 0 8 的父节点1满足  
对于5来说右子树的高度更高，递归返回的时候已经得到了两个高度，  
所有这个函数还是会返回2  
然后来到3，左子树更高，这个时候要返回从左子树找到的2  
最终程度返回就是2

--------------------

这个程度需要先得到左右子树的高度，又要得到从左子树和右子树找到的符合条件的公共根节点  
所有可以采用引用的方式传递参数，例如程序中的h，而找到的根节点则采用返回值方式，当然也可以采用引用的方式，看着怎么舒服怎么来 看了题解才写出来，决定整理一下

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
    
    #define debug(x) cout<<#x<<": "<<(x)<<endl;
    
    class Solution { 
    public:
        
        TreeNode* lcaDeepestLeaves(TreeNode* root) { 
            int h=0;
            return findw(root,h);
        }
        
        TreeNode* findw(TreeNode*r,int& h){ 
            if(r == nullptr){ 
                return nullptr;
            }
            
            int lh=0,rh=0;
            auto lr = findw(r->left,lh);
            auto rr = findw(r->right,rh);
            
            h = 1 + max(lh,rh);
            //debug(r->val)
                //debug(h)
            if(lh < rh){ 
                return rr;
            }else if(lh > rh){ 
                return lr;
            }else{ 
                return r;
            }
            return nullptr;
        }
    };

![在这里插入图片描述][20210410211757619.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]: /images/20221022/c019f5f06c814adb875188f8aa6d87ad.png
[Link 1]: https://leetcode-cn.com/problems/lowest-common-ancestor-of-deepest-leaves/solution/di-gui-c-po-su-de-di-gui-yu-hou-xu-bian-ndsrr/
[20210410211757619.png]: /images/20221022/519a84c8fcdd40a6834cc96b004ca0fd.png