Use post order traverse the binary tree to solve with detailed explain,easy to understand way


  • 0
    C

    explain:
    when we use a stack to traverse the binary tree, once meet the node , a path which is from root to this node displayed . Also ,we find the two nodes' path ,then, we reversely traverse the stack ,the first same node is the LCA

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    	if (root == null || root == p || root == q) {
    		return root;
    	}
    	List<TreeNode> first = new ArrayList<TreeNode>();
    	List<TreeNode> second = new ArrayList<TreeNode>();
    	getPath(root, p, first);
    	getPath(root, q, second);
    	return getCommonNode(first, second);
    }
    
    private TreeNode getCommonNode(List<TreeNode> first, List<TreeNode> second) {
    	for (int i = first.size()-1; i >=0 ; i--) {
    		TreeNode temp = first.get(i);
    		for(int j=second.size()-1; j>=0; j--){
    			if(temp == second.get(j)){
    				return temp;
    			}
    		}
    	}
    
    	return null;
    }
    
    private void getPath(TreeNode root, TreeNode node, List<TreeNode> path) {
    	TreeNode temp = root;
    	
    	do{
    		while(temp != null){
    			path.add(temp);
    			if(node == temp){
    				return;
    			}
    			temp = temp.left;
    		}
    		
    		TreeNode t = null;
    		boolean flag = true;
    		
    		while(flag && path.size() > 0){
    			temp = path.get(path.size()-1);
    			if(temp.right == t){
    				t = path.remove(path.size()-1);
    			}else{
    				flag = false;
    				temp = temp.right;
    			}
    		}
    		
    	}while(path.size() > 0);
    	
    }

Log in to reply
 

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