Day31——二叉树专题

╰+攻爆jí腚メ 2024-04-01 18:23 63阅读 0赞

#### 文章目录 ####

*   *   *   *  25.二叉搜索树中的众数
             *  26.二叉树的最近公共祖先
             *  27. 二叉搜索树的最近公共祖先

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

##### 25.二叉搜索树中的众数 #####

题目链接：[501. 二叉搜索树中的众数 - 力扣（LeetCode）][501. _ - _LeetCode]

**思路**：利用二叉搜索树的特性，采用中序遍历。二叉搜索数的性质进行求解（双指针比较当前节点和前驱节点，计数, 更新等）

**代码实现思路**：

class Solution {
        
        List<Integer> list = new ArrayList<>();
        int pre = -1;
        int count = 0;
        int Maxcount = 0;
        public int[] findMode(TreeNode root) {
        
            dfs(root);
            int[] res = new int[list.size()];
            for(int i = 0;i<list.size();i++){
        
                res[i] = list.get(i);
            }
            return res;
        }
        public void dfs(TreeNode root){
        
            if(root==null){
        
                return ;
            }
            //向左遍历
            dfs(root.left);
            if(root.val==pre){
        
                count++;
            }else{
        
                count = 1;
            }
            pre = root.val;
            if(count==Maxcount){
        
                list.add(root.val);
            }else if(count>Maxcount){
        
                Maxcount = count;
                list.clear();
                list.add(root.val);
            }
            dfs(root.right);
        }
    }

##### 26.二叉树的最近公共祖先 #####

**题目链接**：[236. 二叉树的最近公共祖先 - 力扣（LeetCode）][236. _ - _LeetCode]

**思路**：dfs后序遍历，从低往上搜索公共祖先

1.  求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从低向上的遍历方式。
2.  在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。

class Solution {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            return dfs(root,p,q);
        }
        public TreeNode dfs(TreeNode root,TreeNode p,TreeNode q){
        
            if(root==null||root==p||root==q){
        
                return root;
            }
            //后序遍历
            TreeNode left = dfs(root.left,p,q);
            TreeNode right = dfs(root.right,p,q);
            if(left==null&&right==null){
        
                return null;
            }
            else if(right!=null&&left==null){
        
                return right;
            }
            else if(right==null&&left!=null){
        
                return left;
            }
            else{
        
                return root;
            }
        }
    }

##### 27. 二叉搜索树的最近公共祖先 #####

题目链接：[235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）][235. _ - _LeetCode]

思路：利用二叉搜索树的性质：左子树的值都比跟小，右子树的值都比根大，这样我们就可以确定搜索的方向了！

*  如果当前根节点`root`的值 比 `q p`大，那么说明`p q`的最近公共节点在左子树，我们遍历左子树即可
 *  如果当前根节点`root`的值 比 `q p`小，那么说明`p q`的最近公共节点在右子树，我们遍历左子树即可
 *  `p q`各位于当前`root`的左右子树，那么此时`root`即为最近公共祖先

**Code**:

**递归法**：

class Solution {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            return dfs(root, p, q);
        }
        public TreeNode dfs(TreeNode root, TreeNode p, TreeNode q){
        
            if(root==null){
        
                return null;
            }
            if(root.val>p.val&&root.val>q.val){
        
                return dfs(root.left,p,q);
            }else if(root.val<p.val&&root.val<q.val){
        
                return dfs(root.right,p,q);
            }
            return root;
        }
    }

**迭代法**：

class Solution {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            while(true){
        
                if(root.val>p.val&&root.val>q.val){
        
                    root = root.left;
                }
                else if(root.val<p.val&&root.val<q.val){
        
                    root = root.right;
                }else{
        
                    break;
                }
            }
            return root;
        }
    }

[501. _ - _LeetCode]: https://leetcode.cn/problems/find-mode-in-binary-search-tree/
[236. _ - _LeetCode]: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
[235. _ - _LeetCode]: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/