树-路径相关问题|树

1、树的路径有多种定义：

• 从根节点开始到叶节点的结束的一个序列，显然路径的个数为根节点的个数。
• 从任意一个节点出发，任意一个节点结束。

2、树路径相关的问题：

• 输入一棵二叉树和一个整数， 打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。二叉树中和为某一值的路径

解法：采用前序遍历和一个辅助栈，每次访问到节点都入栈，到了叶节点，计算和是否和参数一样，一样把栈全部数据输出（这里不是弹栈）

template <typename T>
void GetSumPath1(T Tree,int Sum,Stack<ElemType> &MyStack,int TempSum=0)
{
    //只有空树会到这里来，叶节点都被下面承包了，不会达到叶节点后面
    if (Tree==NULL)
    {
        return;
    }

    //计算当前的和
    TempSum += Tree->data;

    //当前路径最后一个节点入栈
    MyStack.push(Tree->data);

    //判断是否是叶节点
    if ((Tree->lchild==NULL)&&(Tree->rchild==NULL))
    {
        if (Sum==TempSum)
        {
            //输出序列
            MyStack.GetAllStackDataInNormalOrderWithoutPop();
        }
    }
    else
    {
        GetSumPath1(Tree->lchild,Sum,MyStack,TempSum);
        GetSumPath1(Tree->rchild,Sum,MyStack,TempSum);
    }

    MyStack.pop();
}

template <typename T>
void GetSumPath(T Tree,int Sum)
{
    Stack<ElemType> MyStack(100);

    GetSumPath1(Tree,Sum,MyStack);

    //MyStack.~Stack();
};

void GetAllStackDataInNormalOrderWithoutPop()
    {
        for (int i=0;i<HeadPtr;i++)
        {
            printf("%d  ",Buff[i]);
        }
        printf("\n");
    }

Python版本：

# 输出路径的和为某个值
    def get_fixed_sum_paths(self,root,sum,buff = None):
        if not root:
            return

        if buff is None:
            buff = []

        buff.append(root.data)
        sum -= root.data

        if not (root.lc or root.rc):
            if sum == 0 and len(buff) > 0 :
                print(buff)
            buff.pop()
            return

        self.get_fixed_sum_paths(root.lc,sum,buff)
        self.get_fixed_sum_paths(root.rc,sum,buff)
        buff.pop()