Given two nodes that are in a binary tree (this is guaranteed) find the shortest traversal path between them.
Solution1:
先用LCA找到ancestor，然后打印path。
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public static List shortestPath(TreeNode root, TreeNode A, TreeNode B) {
if(root == null) {
return null;
}
Stack pathL = new Stack();
Stack pathR = new Stack();
TreeNode ancestor = lowestCommonAncestor(root, A, B);
TreeNode node = ancestor;
helper(node.left, A, B, pathL);
helper(node.right, A, B, pathR);
pathL.push(node);
while(!pathR.isEmpty()) {
pathL.push(pathR.pop());
}
for(TreeNode t: pathL) {
System.out.print(t.val + " ");
}
return pathL;
}
public static boolean helper(TreeNode root, TreeNode A, TreeNode B, Stack path) {
if(root == null) {
return false;
}
if(root.val == A.val || root.val == B.val) {
path.push(root);
return true;
}
if (helper(root.left, A, B, path) || helper(root.right, A, B, path)) { //DFS
path.push(root);
return true;
}
return false;
}
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
if(root == null) {
return null;
}
if(root == A || root == B) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, A, B);
TreeNode right = lowestCommonAncestor(root.right, A, B);
if(left != null && right != null) { // if A and B are on both sides
return root;
}
if(left != null) { // either one of A,B is on one side OR A,B is not in L&R subtrees
return left;
}else {
return right;
}
}
From Han Chen
Solution2:
package leetcode;
import java.util.*;
import java.lang.*;
import java.io.*;
class TreeNode {
public int val;
public TreeNode left, right;
public TreeNode(int val) {
this.val = val;
this.left = this.right = null;
}
}
class Shibai
{
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
if (A == root) {
return root;
}
if (B == root) {
return root;
}
if (root == null) return root;
TreeNode left = lowestCommonAncestor(root.left,A,B);
TreeNode right = lowestCommonAncestor(root.right,A,B);
if (left == null && right == null) return null;
if (left != null && right != null) {
return root;
}
if (left != null) {
return left;
}else {
return right;
}
}
public static TreeNode p(TreeNode r, TreeNode t,List arr) {
if (r == t || r == null) return r;
TreeNode left = p(r.left,t,arr);
TreeNode right = p(r.right,t,arr);
if (left != null || right != null) {
arr.add(r);
}
return left != null? left:right;
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
TreeNode root1 = new TreeNode(1);
TreeNode root2 = new TreeNode(2);
TreeNode root3 = new TreeNode(3);
TreeNode root4 = new TreeNode(4);
TreeNode root5 = new TreeNode(5);
TreeNode root6 = new TreeNode(6);
TreeNode root7 = new TreeNode(7);
TreeNode root8 = new TreeNode(8);
root1.left = root2;
root1.right = root3;
root2.left = root4;
root2.right = root5;
root3.left = root6;
root3.right = root7;
root6.left = root8;
List arr1 = new ArrayList();
List arr2 = new ArrayList();
TreeNode A = root4;
TreeNode B = root8;
TreeNode lca = lowestCommonAncestor(root1,A,B);
//arr1.addAll(arr2);
arr1.add(A);
TreeNode t1 = p(lca,A,arr1);
TreeNode t2 = p(lca,B,arr2);
Collections.reverse(arr2);
arr2.add(B);
arr2.remove(0);
for (int i = 0; i < arr1.size(); i++) {
System.out.println(arr1.get(i).val);
}
System.out.println("-------");
for (int i = 0; i < arr2.size(); i++) {
System.out.println(arr2.get(i).val);
}
}
}
From Shibai
