leetcode-236-二叉树的最近公共祖先-java

题目及测试

package pid236;
/*二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]

 

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

}*/
public class main {
	
	public static void main(String[] args) {
		Object[] x=new Object[]{3,5,1,6,2,0,8,null,null,7,4};	
		BinaryTree tree=new BinaryTree(x);
		tree.printTree(tree.root);
		test(tree.root,tree.root.left,tree.root.right);
		
		test(tree.root,tree.root.left,tree.root.left.right.right);
	}
		 
	private static void test(TreeNode ito,TreeNode ito2,TreeNode ito3) {
		Solution solution = new Solution();
		TreeNode rtn;
		long begin = System.currentTimeMillis();
		rtn = solution.lowestCommonAncestor(ito,ito2,ito3);//执行程序
		long end = System.currentTimeMillis();		
		System.out.println("rtn=" );
		System.out.print(rtn.val);
		System.out.println();
		System.out.println("耗时：" + (end - begin) + "ms");
		System.out.println("-------------------");
	}

}
           

解法1（成功，25ms，很慢）

先使用递归的方法，找到节点在root树中的位置，然后依次把节点和它的parent与i关联，放入map中。

然后查询节点p是否在q的parent列表中，如果不在，查询p的parent，以此类推

package pid236;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.PrimitiveIterator.OfDouble;

/**
 * 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) {
		HashMap<Integer, TreeNode> mapP=new HashMap<>();
		HashMap<TreeNode, Integer> mapQ=new HashMap<>();
		findNode(p, root, mapP, 0);
		findNode2(q, root, mapQ, 0);
		int size=mapP.size();
		for(int i=size-1;i>=0;i--){
			TreeNode parentP=mapP.get(i);
			if(mapQ.containsKey(parentP)){
				return parentP;
			}
		}								
        return root;
    }
	
	public boolean findNode(TreeNode find,TreeNode root,HashMap<Integer, TreeNode> map,int i){
		if(find==null||root==null){
			return false;
		}
		if(find==root){
			map.put(i, root);
			return true;
		}
		if(findNode(find, root.left, map, i+1)){
			map.put(i, root);
			return true;
		}else{
			if(findNode(find, root.right, map, i+1)){
				map.put(i, root);
				return true;
			}
		}
		return false;
	}
	
	public boolean findNode2(TreeNode find,TreeNode root,HashMap<TreeNode, Integer> map,int i){
		if(find==null||root==null){
			return false;
		}
		if(find==root){
			map.put(root, i);
			return true;
		}
		if(findNode2(find, root.left, map, i+1)){
			map.put(root, i);
			return true;
		}else{
			if(findNode2(find, root.right, map, i+1)){
				map.put(root, i);
				return true;
			}
		}
		return false;
	}
}
           

解法2（成功，7ms，极快）

这种方法非常直观。先深度遍历改树。当你遇到节点 p 或 q 时，返回一些布尔标记。该标志有助于确定是否在任何路径中找到了所需的节点。最不常见的祖先将是两个子树递归都返回真标志的节点。它也可以是一个节点，它本身是p或q中的一个，对于这个节点,子树递归返回一个真标志。

从根节点开始遍历树。

如果当前节点本身是 p 或 q 中的一个，我们会将变量 mid 标记为 true，并继续搜索左右分支中的另一个节点。

如果左分支或右分支中的任何一个返回 true，则表示在下面找到了两个节点中的一个。

如果在遍历的任何点上，左、右或中三个标志中的任意两个变为 true，这意味着我们找到了节点 p 和 q 的最近公共祖先。

就是如果节点不是p或q的父节点，三个标志都为false。

只是一个的父节点，1个标志为true。

正好是2个的最近父节点，2个标志为true。

2个的非最近父节点，一定只有一个标志为true，因为2个节点一定在它的left或right侧。

TreeNode result = null;
	
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		hasPorQ(root, p, q);						
        return result;
    }
	
	private int hasPorQ(TreeNode root, TreeNode p, TreeNode q) {
		if(root == null) {
			return 0;
		}
		int mid = 0;
		if(root == p) {
			mid = 1;
		}
		if(root == q) {
			mid = 1;
		}
		int left = hasPorQ(root.left, p, q);
		int right = hasPorQ(root.right, p, q);
		int total = mid + left + right;
		if(total == 2) {
			result = root;
		}
		if(total >= 1) {
			return 1;
		}else {
			return 0;
		}
	}
           

解法3（别人的）

使用父指针迭代

如果每个节点都有父指针，那么我们可以从 p 和 q 返回以获取它们的祖先。在这个遍历过程中，我们得到的第一个公共节点是 LCA 节点。我们可以在遍历树时将父指针保存在字典中。

从根节点开始遍历树。

在找到 p 和 q 之前，将所有节点的父指针存储在字典中。

 一旦我们找到了 p 和 q，我们就可以使用父亲字典获得 p 的所有祖先，并添加到一个称为祖先的集合中。

同样，我们遍历节点 q 的祖先。如果祖先存在于为 p 设置的祖先中，这意味着这是 p 和 q 之间的第一个共同祖先（同时向上遍历），因此这是 LCA 节点。

class Solution {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        // Stack for tree traversal
        Deque<TreeNode> stack = new ArrayDeque<>();

        // HashMap for parent pointers
        Map<TreeNode, TreeNode> parent = new HashMap<>();

        parent.put(root, null);
        stack.push(root);

        // Iterate until we find both the nodes p and q
        while (!parent.containsKey(p) || !parent.containsKey(q)) {

            TreeNode node = stack.pop();

            // While traversing the tree, keep saving the parent pointers.
            if (node.left != null) {
                parent.put(node.left, node);
                stack.push(node.left);
            }
            if (node.right != null) {
                parent.put(node.right, node);
                stack.push(node.right);
            }
        }

        // Ancestors set() for node p.
        Set<TreeNode> ancestors = new HashSet<>();

        // Process all ancestors for node p using parent pointers.
        while (p != null) {
            ancestors.add(p);
            p = parent.get(p);
        }

        // The first ancestor of q which appears in
        // p's ancestor set() is their lowest common ancestor.
        while (!ancestors.contains(q))
            q = parent.get(q);
        return q;
    }

}

           

解法4（别人的）

无父指针的迭代

在前面的方法中，我们在回溯过程中遇到 LCA。我们可以摆脱回溯过程本身。在这种方法中，我们总是有一个指向可能 LCA 的指针，当我们找到两个节点时，我们返回指针作为答案。

从根节点开始。

将 (root, root_state) 放在堆栈上。root_state 定义要遍历该节点的一个子节点还是两个子节点。

当堆栈不为空时，查看堆栈的顶部元素，该元素表示为 (parent_node, parent_state)。

在遍历 parent_node 的任何子节点之前，我们检查 parent_node 本身是否是 p 或 q 中的一个。

当我们第一次找到 p 或 q 的时候，设置一个布尔标记，名为 one_node_found 为 true 。还可以通过在变量 LCA_index 中记录堆栈的顶部索引来跟踪最近的公共祖先。因为堆栈的所有当前元素都是我们刚刚发现的节点的祖先。

第二次 parent_node == p or parent_node == q 意味着我们找到了两个节点，我们可以返回 LCA node。

每当我们访问 parent_node 的子节点时，我们将 (parent_node, updated_parent_state) 推到堆栈上。我们更新父级的状态为子级/分支已被访问/处理，并且相应地更改状态。

当状态变为 BOTH_DONE 时，最终会从堆栈中弹出一个节点，这意味着左、右子树都被推到堆栈上并进行处理。如果 one_node_found 是 true 的，那么我们需要检查被弹出的顶部节点是否可能是找到的节点的祖先之一。在这种情况下，我们需要将LCA_index减少一个。因为其中一位祖先被弹出了。

当同时找到 p 和 q 时，LCA_index 将指向堆栈中包含 p 和 q 之间所有公共祖先的索引。并且 LCA_index 元素具有p和q之间的最近公共祖先。

class Solution {

    // Three static flags to keep track of post-order traversal.

    // Both left and right traversal pending for a node.
    // Indicates the nodes children are yet to be traversed.
    private static int BOTH_PENDING = 2;

    // Left traversal done.
    private static int LEFT_DONE = 1;

    // Both left and right traversal done for a node.
    // Indicates the node can be popped off the stack.
    private static int BOTH_DONE = 0;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        Stack<Pair<TreeNode, Integer>> stack = new Stack<Pair<TreeNode, Integer>>();

        // Initialize the stack with the root node.
        stack.push(new Pair<TreeNode, Integer>(root, Solution.BOTH_PENDING));

        // This flag is set when either one of p or q is found.
        boolean one_node_found = false;

        // This is used to keep track of the LCA.
        TreeNode LCA = null;

        // Child node
        TreeNode child_node = null;

        // We do a post order traversal of the binary tree using stack
        while (!stack.isEmpty()) {

            Pair<TreeNode, Integer> top = stack.peek();
            TreeNode parent_node = top.getKey();
            int parent_state = top.getValue();

            // If the parent_state is not equal to BOTH_DONE,
            // this means the parent_node can't be popped off yet.
            if (parent_state != Solution.BOTH_DONE) {

                // If both child traversals are pending
                if (parent_state == Solution.BOTH_PENDING) {

                    // Check if the current parent_node is either p or q.
                    if (parent_node == p || parent_node == q) {

                        // If one_node_found was set already, this means we have found
                        // both the nodes.
                        if (one_node_found) {
                            return LCA;
                        } else {
                            // Otherwise, set one_node_found to True,
                            // to mark one of p and q is found.
                            one_node_found = true;

                            // Save the current top element of stack as the LCA.
                            LCA = stack.peek().getKey();
                        }
                    }

                    // If both pending, traverse the left child first
                    child_node = parent_node.left;
                } else {
                    // traverse right child
                    child_node = parent_node.right;
                }

                // Update the node state at the top of the stack
                // Since we have visited one more child.
                stack.pop();
                stack.push(new Pair<TreeNode, Integer>(parent_node, parent_state - 1));

                // Add the child node to the stack for traversal.
                if (child_node != null) {
                    stack.push(new Pair<TreeNode, Integer>(child_node, Solution.BOTH_PENDING));
                }
            } else {

                // If the parent_state of the node is both done,
                // the top node could be popped off the stack.
                // Update the LCA node to be the next top node.
                if (LCA == stack.pop().getKey() && one_node_found) {
                    LCA = stack.peek().getKey();
                }

            }
        }

        return null;
    }
}