JAVA 14ms clear and do better.


  • 0
    J
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public  TreeNode lowestCommonAncestor(TreeNode root, TreeNode p,
    			TreeNode q) {
    		ArrayList<TreeNode> path1 = new ArrayList<>();
    		ArrayList<TreeNode> path2 = new ArrayList<>();
    		boolean find1 = findpath(root, p, path1);
    		boolean find2 = findpath(root, q, path2);
    		if(find1&&find2){
    			TreeNode ans = null;
    			for(int i =0;i<Math.min(path1.size(),path2.size());i++){
    				if(path1.get(i).val!=path2.get(i).val){
    					break;
    				}else{
    					ans = path1.get(i);
    				}	
    			}
    			return ans;	
    		}
    		return null;
    	}
    
    	public static boolean findpath(TreeNode root,TreeNode nood,ArrayList<TreeNode> path){
    		  if(root==null) return false;
    		  path.add(root);
    		  if(root.val ==nood.val) return true;
    	      //左子树或右子树 是否找到,找到的话当前节点就在路径中
    		  boolean find =  ( findpath(root.left,nood,path) || findpath(root.right,nood,path) );
    		  if(find) return true;
    		  //该节点下未找到就弹出
    		  path.remove(path.size()-1);
    		  return false;
    }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.