二叉树求两个结点的父节点及一个结点的所有祖先结点

求两个结点的父节点

有一个比较简单的方法是遍历二叉树数，判断结点的左右结点是否为给出结点。这里采用另外一种方法：

public static<T> BinaryTreeNode<T> LCA(BinaryTreeNode<T> root, BinaryTreeNode<T> a, BinaryTreeNode<T> b){ // 查找a,b结点的父结点 BinaryTreeNode<T> left,right; if(root == null) return root; if(root.data == a.data || root.data == b.data) return root; left = LCA(root.getLeft(),a,b); right = LCA(root.getRight(),a,b); if(left != null && right != null) return root; else return left == null ? right : left; }

求给出结点的所有祖先结点

给出一个结点，求所有的祖先结点，也可以理解为求根节点到该节点的路径。

public static<T> int printAllAncestors(BinaryTreeNode<T> root, BinaryTreeNode<T> node){ // 求结点node的所有祖先结点 if(root == null || root.getLeft() == null || root.getRight() == null) return 0; if(root.getLeft().data == node.data || root.getRight().data == node.data || printAllAncestors(root.getLeft(),node) == 1 || printAllAncestors(root.getRight(), node) == 1){ System.out.println(root.getData()); return 1; } return 0; }

完整代码可以访问我的GitHub：https://github.com/StriverLi/Data-Structures-and-Algorithms-in-Java/blob/master/src/tree/BinaryTreeNode.java