- 剑指 Offer 面试题 25（Java 版）：二叉树中和为某一值的路径
题目：输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的所有的结点形成一条路径。
如下图，输入二叉树和整数22，则打印出两条路径，第一条路径包含结点10，12，第二条路径包含的结点为10，5，7。
例子
思路：既然要从根结点开始遍历，那么就采用前序遍历的方法就行，而且还要计算各个结点的和，那么就需要一个容器装这些结点的值。通过模拟几次，发现有些路径是不符合的，需要返回上一结点，这时候我们选择使用栈作为容器，当遍历到叶子结点的时候，如果值不符合，那就返回上一结点，遍历另外一边。
show my code
/**
* 查找二叉树某一路径的值的和为一个整数
* @author innovator
*
*/
public class FindPath {
public static void findCertainPath(BinaryTreeNode root,int expectedNum){
if(root == null){
return;
}
Stack<Integer> path = new Stack<>();
findAPath(root, expectedNum, path);
}
/**
* 前序遍历直到叶子结点
* @param root
* @param expectedNum
* @param path
*/
public static void findAPath(BinaryTreeNode root,int expectedNum,Stack<Integer> path){
if(root == null){
return;
}
//判断是否为叶子结点
boolean isLeaf = (root.leftNode == null && root.rightNode == null);
//遍历到了叶子结点，判断值是否符合要求
if(isLeaf){
if(root.value == expectedNum){
System.out.println("找到了路径");
for(Integer i:path){
System.out.println("结点："+i);
}
System.out.println(root.value);
}
}else{
//不是叶子结点，包含子树
path.add(root.value);
//继续遍历下去，遍历到叶子结点
findAPath(root.leftNode, expectedNum - root.value, path);
findAPath(root.rightNode, expectedNum - root.value, path);
//遍历完了左右叶子结点，弹出这个根结点
path.pop();
}
}
public static void main(String[] args){
BinaryTreeNode root1 = new BinaryTreeNode(8);
BinaryTreeNode node1 = new BinaryTreeNode(8);
BinaryTreeNode node2 = new BinaryTreeNode(7);
BinaryTreeNode node3 = new BinaryTreeNode(9);
BinaryTreeNode node4 = new BinaryTreeNode(2);
BinaryTreeNode node5 = new BinaryTreeNode(4);
BinaryTreeNode node6 = new BinaryTreeNode(7);
root1.leftNode = node1;
root1.rightNode = node2;
node1.leftNode = node3;
node1.rightNode = node4;
node4.leftNode = node5;
node4.rightNode = node6;
findCertainPath(root1, 25);
}
}
结果
- 剑指 Offer 面试题 27（Java 版）：二叉搜索树与双向链表
题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
比如下图中左边的二叉搜索树，则输出转换之后的排序现向链表。
例子
思路：根据二叉搜索树的特点，我们采用中序递归遍历来转换，先转换左子树，然后连接根结点，最后转换右子树，连接在一起就可以了。
show my code
/**
* 二叉搜索树转成双向链表
* @author innovator
*
*/
public class Tree2LinkedList {
/**
*
* @param root 二叉树的根结点
* @return 双向链表的头结点
*/
public static BinaryTreeNode convert(BinaryTreeNode root){
// 用于保存处理过程中的双向链表的尾结点
BinaryTreeNode[] lastNode = new BinaryTreeNode[1];
convertNode(root, lastNode);
// lastNode此时处于链表末端，需要从尾结点找到双向链表的头结点
BinaryTreeNode head = lastNode[0];
while (head != null && head.leftNode != null) {
System.out.println("尾结点值："+head.value);
head = head.leftNode;
}
return head;
}
/**
*
* @param root 当前的根结点
* @param lastNode 已经处理好的双向链表的尾结点
*/
public static void convertNode(BinaryTreeNode node,BinaryTreeNode[] lastNode){
// 结点不为空
if (node != null) {
// 如果有左子树就先处理左子树
if (node.leftNode != null) {
convertNode(node.leftNode, lastNode);
}
// 将当前结点的前驱指向已经处理好的双向链表（由当前结点的左子树构成）的尾结点
node.leftNode = lastNode[0];
// 如果左子树转换成的双向链表不为空，设置尾结点的后继
if (lastNode[0] != null) {
lastNode[0].rightNode = node;
}
// 记录当前结点为尾结点
lastNode[0] = node;
// 处理右子树
if (node.rightNode != null) {
convertNode(node.rightNode, lastNode);
}
}
}
public static void main(String[] args){
BinaryTreeNode root1 = new BinaryTreeNode(10);
BinaryTreeNode node1 = new BinaryTreeNode(6);
BinaryTreeNode node2 = new BinaryTreeNode(14);
BinaryTreeNode node3 = new BinaryTreeNode(4);
BinaryTreeNode node4 = new BinaryTreeNode(8);
BinaryTreeNode node5 = new BinaryTreeNode(12);
BinaryTreeNode node6 = new BinaryTreeNode(16);
root1.leftNode = node1;
root1.rightNode = node2;
node1.leftNode = node3;
node1.rightNode = node4;
node2.leftNode = node5;
node2.rightNode = node6;
BinaryTreeNode head = convert(root1);
while(head != null){
System.out.println("值："+head.value);
head = head.rightNode;
}
}
}
结果
