LCA---Lowest common ancestor

cooxer 發(fā)布于2019-08-14 17:08 / 741人閱讀

摘要：在為根的二叉樹中找的如果找到了就返回這個如果只碰到，就返回如果只碰到，就返回如果都沒有，就返回三種情況都在左子樹中，都在右子樹中，左右分別在二叉樹的左右子樹找和，找到及返回，根據(jù)和是否存在內(nèi)容決定最低公共祖先終止條件，找到或者，或者到，就在

在root為根的二叉樹中找A,B的LCA:
如果找到了就返回這個LCA
如果只碰到A，就返回A
如果只碰到B，就返回B
如果都沒有，就返回null

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: The root of the binary search tree.
     * @param A and B: two nodes in a Binary.
     * @return: Return the least common ancestor(LCA) of the two nodes.
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
        
         //三種情況： 都在左子樹中， 都在右子樹中， 左右分別
        //在二叉樹的左右子樹找node1和node2， 找到及返回， 根據(jù)left和right是否存在內(nèi)容決定最低公共祖先
        if (root == null || root == node1 || root == node2){
            return root;
        }
        
        TreeNode left = lowestCommonAncestor(root.left, node1, node2);
        TreeNode right = lowestCommonAncestor(root.right, node1, node2);
        
        if (left != null && right != null){
            return root;
        }
        
        if (left != null){
            return left; 
        }
        if (right != null){
            return right;
        }
        else{
            return null;
        }
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        //終止條件， 找到node1或者node2，或者到null node， 就return
        // if (root == null || root == node1 || root == node2) {
        //     return root;
        // }
        
        // Divide （在left child和right child里面找node1和2）
        // TreeNode left = lowestCommonAncestor(root.left, node1, node2);
        // TreeNode right = lowestCommonAncestor(root.right, node1, node2);
        
        // Conquer  
        // if (left != null && right != null) {
        //     return root;
        // } 
        // if (left != null) {
        //     return left;
        // }
        // if (right != null) {
        //     return right;
        // }
        // return null;            //當left sub和right sub都沒有n1或n2
    }
}