二叉树找最近公共父节点

· 385 words · 1 minute read
2017年8月
算法

二叉树是二叉搜索树

对于二叉搜索树，其中序有序。若最后left<head<right,并且left<right，则head为最近公共祖先。

public Node low(Node head, Node o1, Node o2){
        int left = o1.val;
        int right = o2.val;
        while(head != null){
            if(head.val < left){
                head = head.right;
            }else if(head.val > right){
                head = head.left;
            }else{
                return head;
            }
        }
        return null;
    }

二叉树是非二叉搜索树

left为head左子树的返回节点，right为head右子树的返回节点返回节点不代表是子树！！！

  1. 如果发现head是null,o1,o2则返回head.
  2. 如果发现left != null && right != null则说明head是最近父节点，直接返回

  3. 如果left和right有一个为null，另一个不为null,不为null的记为node，此时node要么是o1或o2中的一个，要么就是最近父节点。不管哪种情况直接返回即可。

    //如果是普通的二叉树
public Node lowParent(Node head, Node o1, Node o2){
    if(head == null || head == o1 || head == o2){
        return head;
    }
    Node l = lowParent(head.left,o1,o2);
    Node r = lowParent(head.right,o1,o2);
    if(l != null && r != null){
        return head;
    }
    return l != null ? l : r;
}
Share