面试题【67-68】两个面试案例

面试题67：把字符串转换成整数

题目：请你写一个函数StrToInt，实现把字符串转换成整数这个功能。当然，不能使用atoi或者其他类似的库函数。

    public int myAtoi(String str) {
        if (str == null || (str = str.trim()).length() == 0) {
            return 0;
        }

        int index = 0;
        boolean negative = false;
        if (str.charAt(0) == '-' || str.charAt(0) == '+') {
            index++;
            if (str.charAt(0) == '-') {
                negative = true;
            }
        }

        int result = 0;
        for (int i = index; i < str.length(); i++) {
            if (str.charAt(i) < '0' || str.charAt(i) > '9') {
                return negative ? -result : result;
            } else {
                long temp = (long)result * 10;
                result = result * 10 + (str.charAt(i) - '0');
                if (result < temp) {
                    return negative ? Integer.MIN_VALUE : Integer.MAX_VALUE;
                }
            }
        }
        return negative ? -result : result;
    }

面试题68：树中两个结点的最低公共祖先

题目一：二叉搜索树两个结点的最低公共祖先

• 算法：递归
  • 当根节点的值处于两个节点值中间时即是最低公共祖先
  • 当根节点的值大于两个节点值时最低公共祖先在左子树
  • 当根节点的值小于两个节点值时最低公共祖先在右子树

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

题目二：普通二叉树两个结点的最低公共祖先

题目：输入两个树结点，求它们的最低公共祖先。

• 算法：
  • 递归保存路径
  • 最后一个公共节点
    • 注意：
      • 可能其中一个输入节点是这两个输入节点的公共祖先，需要让保存的路径包括输入节点本点
      • null结点返回false

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || p == null || q == null) {
        return null;
    }

    ArrayList<TreeNode> list1 = new ArrayList<TreeNode>();
    getNodePath(root, p, list1);
    ArrayList<TreeNode> list2 = new ArrayList<TreeNode>();
    getNodePath(root, q, list2);

    return getLastCommonNode(list1, list2);
}
public boolean getNodePath(TreeNode root, TreeNode p, ArrayList<TreeNode> list) {
    if (root == null) {
        return false;
    }
    if (root == p) {
        list.add(root);
        return true;
    }

    list.add(root);
    boolean found = getNodePath(root.left, p, list) || getNodePath(root.right, p, list);
    if (!found) {
        list.remove(list.size()-1);
    }
    return found;
}
TreeNode getLastCommonNode(ArrayList<TreeNode> list1, ArrayList<TreeNode> list2) {
    TreeNode temp = null;
    for (int i = 0; i < list1.size() && i < list2.size(); i++) {
        if (list1.get(i) == list2.get(i)) {
            temp = list1.get(i);
        }
    }
    return temp;
}

题目三：有指向父节点的指针的二叉树的最低公共祖先

• 算法：
  • LeetCode Discuss
  • 使用两个指针进行遍历，当一个指针到头时，就重置它为另一个链表的头节点
  • 当两个链表长度相同时：不到一轮遍历既能找到答案
  • 当两个链表长度不同时：不到二轮遍历既能找到答案

public TreeNode2 lowestCommonAncestor(TreeNode2 root, TreeNode2 p, TreeNode2 q) {
    if (root == null || p == null || q == null) {
        return null;
    }

    TreeNode2 a = p;
    TreeNode2 b = q;
    while (a != b) {
        a = (a == null) ? q : a.parent;
        b = (b == null) ? p : b.parent;
    }
    return a;
}