【剑指offer第19天】搜索与回溯算法

川长思鸟来 2022-09-14 00:16 120阅读 0赞

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

先看特殊情况：二叉搜索树  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16]  
二叉搜索树特性，左子树都比根节点数值大，右子树比根节点数值小。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            if(root == null){ 
                return null;
            }
            if(root.val > p.val&&root.val > q.val){ 
                return lowestCommonAncestor(root.left,p,q);
            }
            if(root.val < p.val && root.val < q.val){ 
                return lowestCommonAncestor(root.right,p,q);
            }
            return root;
        }
    }

迭代法求解，可以提前返回，缩小时间复杂度：

class Solution { 
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            while(root != null) { 
                if(root.val < p.val && root.val < q.val) // p,q 都在 root 的右子树中
                    root = root.right; // 遍历至右子节点
                else if(root.val > p.val && root.val > q.val) // p,q 都在 root 的左子树中
                    root = root.left; // 遍历至左子节点
                else break;
            }
            return root;
        }
    }

如果是普通二叉树：  
当搜索到左右都不为空时返回的结点即为最近的公共祖先结点。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            if(root == null){ 
                return null;
            }
            if(root.val == p.val||root.val == q.val){ 
                return root;
            }
            TreeNode left = lowestCommonAncestor(root.left,p,q);
            TreeNode right = lowestCommonAncestor(root.right,p,q);
            if(left!=null&&right!=null){ 
                return root;
            }else if(left != null){ 
                return lowestCommonAncestor(root.left,p,q);
            }else if(right != null){ 
                return lowestCommonAncestor(root.right,p,q);
            }
            return null;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/89baf65c8bb545768daf4de9f7bed502.png