剑指offer面试题系列

题目：输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。从树的根节点往下一直到叶节点所经过的节点形成一条路径。

分析

思路：

因为是寻找符合条件的路径，所以一路上遍历过的节点必须存储下来，这个存储结构我选择了LinkedList，因为它既可以当栈使用，也可以当队列使用，很方便。

此题最关键的地方，我觉得应该是判断叶子节点那一部分和怎么出栈那一部分。

遍历节点，如果是叶子节点，看sum，如果等于给定的数值，则打印该路径；否则将该节点出栈。如果遇到 sum 大于num的情况，则直接退出当前函数。

此题的技巧是：每次遍历一个结点时，不管此节点满足条件与否，都将其入队，在函数退出时，随着函数一起退栈，这样做的目的是为了保持一致性：节点满足路径条件，则将其打印后，出栈该结点，再遍历下一个结点；如果不满足，也将其出栈，这样就不会造成找到路径和没有找到路径两种情况处理不统一的问题（刚开始就在这里纠缠，导致代码很臃肿，同时逻辑也混乱。）

一句话：深刻理解递归是解出来此题的关键。递归实质上就是一个出栈入栈的过程。

代码

package com.tree;

import java.util.ArrayList;
import java.util.LinkedList;

class TNode {
    int data;
    TNode left;
    TNode right;

    public TNode(int data) {
        this.data = data;
        this.left = this.right = null;
    }
}

/* 找出二叉树中等于某一值的所有路径 */
public class TreePath {
    public static void AddPath(TNode tnode, LinkedList<TNode> list, int sum,
            int num) {
        if (tnode == null)
            return;
        list.offer(tnode);
        if (tnode.left == null && tnode.right == null) { // leaf node
            if (sum + tnode.data == num) {
                PrintPath(list);
            } 

        } else { // non-leaf node
            if (tnode.data + sum < num) {
                sum += tnode.data;
                AddPath(tnode.left, list, sum, num);
                AddPath(tnode.right, list, sum, num);
            }
        }
        list.pollLast();
    }

    public static void PrintPath(LinkedList<TNode> list) {
        int i;
        for (i = 0; i < list.size(); i++) {
            System.out.print(list.get(i).data + "---");
        }
        System.out.println("NULL");
    }

    public static TNode BuildTree(int[] arr) {
        ArrayList<TNode> nodelist = new ArrayList<TNode>();
        if (arr == null)
            return null;
        if (arr.length == 1) { // 如果数组中只有一个元素
            TNode root = new TNode(arr[0]);
            return root;
        }

        // 将数组转化成二叉树结点
        for (int i = 0; i < arr.length; i++) {
            nodelist.add(new TNode(arr[i]));
        }

        TNode root = nodelist.get(0);
        for (int j = 0; j < arr.length / 2 - 1; j++) {
            nodelist.get(j).left = nodelist.get(2 * j + 1);
            nodelist.get(j).right = nodelist.get(2 * j + 2);
        }
        int lastParentIndex = arr.length / 2 - 1;
        nodelist.get(lastParentIndex).left = nodelist
                .get(2 * lastParentIndex + 1);
        if (arr.length % 2 == 1)
            nodelist.get(lastParentIndex).right = nodelist
                    .get(2 * lastParentIndex + 2);

        return root;
    }

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 3, 5, 4, 8, 2 };
        int[] arr2 = { 15 };
        int[] arr1 = { 1, 2, 3, 6, 5, 4 };
        TNode root = BuildTree(arr);
        LinkedList<TNode> list = new LinkedList<TNode>();
        AddPath(root, list, 0, 9);
        if(list.isEmpty())
            System.out.println("Sorry there is no path");
    }
}

备注

总结

说实话，这道题可能是做剑指offer以来，感觉最无头绪的一道题。刚拿到这个题的时候，完全没有感觉，不知道怎么去做。现在竟然没有看答案就做出来了，这样的感觉很好，又给自己增加一点点自信，继续保持！

PS : 看了剑指offer的分析过程，想到遇到这种可以用递归的方法解决问题的时候，尽量列表格，填写变量的值，这样可以更快的找到规律。