給一個(gè)binary tree括饶，每一個(gè)node含有parent指向parent，給定一個(gè)node来涨，找出他右側(cè)的node图焰。
用了dfs，順著左蹦掐，右技羔，父的順序找僵闯，標(biāo)記了高度。
package snapchat;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
public class FindNeighborNode {
public TreeNode findNeighbor(TreeNode self){
TreeNode p = self.parent;
if(p == null)return null;
Set<TreeNode> visited = new HashSet<>();
visited.add(self);
return findLeftMost(self,0,0,visited);
}
public TreeNode findLeftMost(TreeNode cur, int curHeight,int targetHeight,Set<TreeNode> visited){
if(!visited.contains(cur) && curHeight == targetHeight)return cur;
visited.add(cur);
if(cur.left != null && !visited.contains(cur.left)){
TreeNode l = findLeftMost(cur.left,curHeight - 1, targetHeight,visited);
if(l != null)return l;
}
if(cur.right != null && !visited.contains(cur.right)){
TreeNode r = findLeftMost(cur.right,curHeight - 1,targetHeight,visited);
if(r != null)return r;
}
if(cur.parent != null && !visited.contains(cur.parent)){
TreeNode p = findLeftMost(cur.parent,curHeight + 1,targetHeight,visited);
if(p != null)return p;
}
return null;
}
public static void main(String[] args){
FindNeighborNode fnn = new FindNeighborNode();
TreeNode root = new TreeNode(10);
TreeNode t5 = root.left = new TreeNode(5);
root.left.parent = root;
TreeNode t15 = root.right = new TreeNode(15);
root.right.parent = root;
TreeNode t3 = root.left.left = new TreeNode(3);
TreeNode t1 = root.left.left.left = new TreeNode(1);
TreeNode t12 = root.right.left = new TreeNode(12);
TreeNode t14 = root.right.left.right = new TreeNode(14);
t3.parent = t5;
t1.parent = t3;
t12.parent = t15;
t14.parent = t12;
TreeNode res = fnn.findNeighbor(t1);
System.out.println(res.val);
}
}
