微软面试100题(4):二元树中找出和为某一值的所有路径

4.在二元树中找出和为某一值的所有路径
题目：输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如 输入整数22和如下二元树
  10   
  / \   
  5 12   
  / \   
  4 7
则打印出两条路径：10, 12和10, 5, 7。

这道题的递归显然是很简单，先序遍历，同时用一个栈保存所经过的路径，当和为指定值的时候就输出

非递归算法随便搜了下没有看到，费了比较大精力才写出来。

核心问题是对于非递归的先序遍历，存储路径的栈并不是存储的全路径，实际当走到某个节点的右结点时，该节点已经从出栈了，所以这个栈里路径是不对的，并不能使用。

解决方法有2个：

1.保存一个访问过的节点的列表，当读到一个节点时，进栈，保持栈中的内容就是全路径，当出栈后，判断栈顶节点的右边是不是已经访问过了，如没访问过，则说明这次该访右边了，反之，则继续出栈。

这个方法的问题是每次读到一个节点，就要遍历一次读过的所有节点，所以对于n个节点的树，其复杂度大概为n^2。这个逻辑比较简单，就不实现了。

2.是保存两个栈，一个s1用于先序遍历，一个s2用于保存从根到当前节点的路径。其复杂度仍然为线性，但是逻辑比较难懂

当读到某个cur节点的右节点时，说明cur以及cur的左边已经读过了，只需读右边部分，这个节点cur从s1出栈（下回只需要处理cur的父结点），但从s2并不出栈.

当cur的左右节点都遍历完成的时，这时s1指向的是cur的parent,s2指向的是cur的右节点。这时对s2出栈，一直到和s1的栈顶元素相同时，继续遍历右边的子树。

/*
 * =====================================================================================
 *
 * Filename: btree.c
 *
 * Description: practice for binary tree
 *
 * Version: 1.0
 * Created: 09/21/2012 09:28:18 PM
 * Revision: none
 * Compiler: gcc
 *
 * Author: [e-mail]
 * Organization:
 *
 * =====================================================================================
 */
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
typedef struct tagNode{
    int value;
    struct tagNode* left;
    struct tagNode* right;
}Node;

Node* CreateBTree2(Node* root, int* numbers, int size){
    if(size == 0) return NULL;
    printf ( "tracking %d\n", *numbers );
    root = (Node*)malloc(sizeof(Node));
    int mid = size/2;
    root-> value = numbers[mid];
    printf ( "fill %p : %d\n", root, root->value );
    root->left =     CreateBTree2(root, numbers, mid);
    root->right = CreateBTree2(root, numbers+mid+1, size - mid -1);
    return root;
}

void GetPathSumNR(Node *head, int tar){
    Node **spath = (Node **)malloc(sizeof(void*)*1000);
    Node **dpath = (Node **)malloc(sizeof(void*)*1000);
    Node **shead = &spath[1];

    *spath= *dpath = NULL;
    int sum = 0;

    Node *root = head;
    while(root || (*dpath)!=NULL){
        while(root){
            dpath++;
            spath++;
            *spath = root;
            *dpath = root;
            printf ( "push %d\n", root->value );
            sum+=root->value;
            if(sum == tar){
                Node **tmp = shead;
                while(*tmp){
                    printf ( "%d -> ", (*tmp)->value );
                    tmp++;
                }
                printf ( "\n" );
            }

            root = root->left;
        }
        if(*dpath){
            root = *dpath;
            root = root->right;
            *dpath =NULL;
            dpath--;
            if(root == NULL) {
                while(*spath != *dpath){
                    sum-= (*spath)->value;
                    printf ( "pop %d\n", (*spath)->value );
                    *spath = NULL;
                    spath--;
                }
            }
        }
    }
}


void GetPathSum(Node * head, int tar, int sum, Node** path, Node **pathhead){
    printf ( "tracking %d\n", head->value );
    if(path == NULL){
        path = (Node **)malloc(sizeof(void*)*1000);
        pathhead = path;
        path --;
    }
    path++;
    *path = head;
    sum += head->value;
    if(sum == tar){
        while(*pathhead){
            printf ( "%d -> ", (*pathhead)->value );
            pathhead++;
        }
        printf ( "\n" );
    }

    if(head->left){
        GetPathSum(head->left, tar, sum, path, pathhead);
    }
    if(head->right){
        GetPathSum(head->right, tar, sum, path, pathhead);
    }
}



/*
 * === FUNCTION ======================================================================
 * Name: main
 * Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    //Create binary tree
    int nums[]= {1,2,3,4,5,6,7,8,9,10};
    printf ( "----------Creating tree----------\n" );
    Node *head = CreateBTree2(NULL, nums, 10);
    //Get the path from root to the node 3

    printf ( "------------sum = 15------------------\n" );
    GetPathSumNR(head,15);


    return EXIT_SUCCESS;
}                /* ---------- end of function main ---------- */