careercup-树与图 4.9

4.9 给定一颗二叉树，其中每个结点都含有一个数值。设计一个算法，打印结点数值总和等于某个给定值的所有路径。注意，路径不一定非得从二叉树的根节点或叶子节点开始或结束。

类似于leetcode：Path Sum II

C++实现代码：（使用了双重的递归）对于不含有parent指针域时。

#include<iostream>

#include<new>

#include<vector>

using namespace std;

//Definition for binary tree

struct TreeNode

{

    int val;

    TreeNode *left;

    TreeNode *right;

    TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Solution

{

public:

    vector<vector<int> > path;

    vector<vector<int> > pathSum(TreeNode *root, int sum)

    {

        vector<int> tmp;

        hasPathSum(root,sum,tmp);

        //改变开始的节点，不一定要从根结点开始，遍历从每一个节点开始

        if(root->left)

            pathSum(root->left,sum);

        if(root->right)

            pathSum(root->right,sum);

        return path;

    }

    void hasPathSum(TreeNode *root, int sum,vector<int> tmp)

    {

        if(root==NULL)

            return;

        tmp.push_back(root->val);

        //改变结束的地方，不一定要到叶子节点

        if((sum-root->val)==)

        {

            path.push_back(tmp);

        }

        if(root->left)

            hasPathSum(root->left,sum-root->val,tmp);

        if(root->right)

            hasPathSum(root->right,sum-root->val,tmp);

    }

    void createTree(TreeNode *&root)

    {

        int i;

        cin>>i;

        if(i!=)

        {

            root=new TreeNode(i);

            if(root==NULL)

                return;

            createTree(root->left);

            createTree(root->right);

        }

    }

};

int main()

{

    Solution s;

    TreeNode *root;

    s.createTree(root);

    vector<vector<int> > path=s.pathSum(root,);

    for(auto a:path)

    {

        for(auto v:a)

            cout<<v<<" ";

        cout<<endl;

    }

}

方法二：如果结点中包含指向父亲结点的指针，那么，只需要去遍历这棵二叉树，然后从每个结点开始，不断地去累加上它父亲结点的值直到父亲结点为空(这个具有唯一性，因为每个结点都只有一个父亲结点。也正因为这个唯一性，可以不另外开额外的空间来保存路径)，如果等于给定的值sum，则打印输出。

实现的方法：

void find_sum(Node* head, int sum){

    if(head == NULL) return;

    Node *no = head;

    int tmp = ;

    for(int i=; no!=NULL; ++i){

        tmp += no->key;

        if(tmp == sum)

            print(head, i);

        no = no->parent;

    }

    find_sum(head->lchild, sum);

    find_sum(head->rchild, sum);

}

打印输出时，只需要提供当前结点的指针，及累加的层数即可。然后从当前结点开始，不断保存其父亲结点的值(包含当前结点)直到达到累加层数，然后逆序输出即可。

代码如下：

void print(Node* head, int level){

    vector<int> v;

    for(int i=; i<level; ++i){

        v.push_back(head->key);

        head = head->parent;

    }

    while(!v.empty()){

        cout<<v.back()<<" ";

        v.pop_back();

    }

    cout<<endl;

}

方法三：如果结点中不包含指向父亲结点的指针，则在二叉树从上向下查找路径的过程中，需要为每一次的路径保存中间结果，累加求和仍然是从下至上的，对应到保存路径的数组，即是从数组的后面开始累加的，这样能保证遍历到每一条路径。

代码如下：

void print2(vector<int> v, int level){

    for(int i=level; i<v.size(); ++i)

        cout<<v.at(i)<<" ";

    cout<<endl;

}

void find_sum2(Node* head, int sum, vector<int> v, int level){

    if(head == NULL) return;

    v.push_back(head->key);

    int tmp = ;

    for(int i=level; i>-; --i){

        tmp += v.at(i);

        if(tmp == sum)

            print2(v, i);

    }

    vector<int> v1(v), v2(v);

    find_sum2(head->lchild, sum, v1, level+);

    find_sum2(head->rchild, sum, v2, level+);

}

方法二完整代码：

#include<iostream>

#include<new>

#include<map>

#include<vector>

using namespace std;

struct BinarySearchTree

{

    int elem;

    BinarySearchTree *parent;

    BinarySearchTree *left;

    BinarySearchTree *right;

    BinarySearchTree(int x):elem(x),parent(NULL),left(NULL),right(NULL) {}

};

void insert(BinarySearchTree *&root,int z)

{

    BinarySearchTree *y=new BinarySearchTree(z);

    if(root==NULL)

    {

        root=y;

        return;

    }

    else if(root->left==NULL&&z<root->elem)

    {

        root->left=y;

        y->parent=root;

        return;

    }

    else if(root->right==NULL&&z>root->elem)

    {

        root->right=y;

        y->parent=root;

        return;

    }

    if(z<root->elem)

        insert(root->left,z);

    else

        insert(root->right,z);

}

void createBST(BinarySearchTree *&root)

{

    int arr[]= {,,,,,,,,,};

    for(auto a:arr)

        insert(root,a);

}

//使用level的原因就是因为，不一定要到根，只有根的父节点为NULL

void print(BinarySearchTree *head,int level)

{

    vector<int> vec;

    for(int i=;i<level;++i)

    {

        vec.push_back(head->elem);

        head=head->parent;

    }

    while(!vec.empty())

    {

        cout<<vec.back()<<" ";

        vec.pop_back();

    }

    cout<<endl;

}

//root选择的是当前结束的节点，也就是从下往上开始最下面的节点，而node是往上找到的刚好满足的最后一个结点，root是在不断加深的

void find_sum(BinarySearchTree *root,int sum)

{

    if(root==NULL)

        return;

    BinarySearchTree *node=root;

    int tmp=;

    for(int i=;node!=NULL;++i)

    {

        tmp+=node->elem;

        if(tmp==sum)

            print(root,i);

        node=node->parent;

    }

    find_sum(root->left,sum);

    find_sum(root->right,sum);

}

int main()

{

    BinarySearchTree *root=NULL;

    createBST(root);

    cout<<"find sum is: "<<endl;

    find_sum(root,);

    return ;

}

方法三完整代码：

#include<iostream>

#include<new>

#include<map>

#include<vector>

using namespace std;

struct BinarySearchTree

{

    int elem;

    BinarySearchTree *parent;

    BinarySearchTree *left;

    BinarySearchTree *right;

    BinarySearchTree(int x):elem(x),parent(NULL),left(NULL),right(NULL) {}

};

void insert(BinarySearchTree *&root,int z)

{

    BinarySearchTree *y=new BinarySearchTree(z);

    if(root==NULL)

    {

        root=y;

        return;

    }

    else if(root->left==NULL&&z<root->elem)

    {

        root->left=y;

        y->parent=root;

        return;

    }

    else if(root->right==NULL&&z>root->elem)

    {

        root->right=y;

        y->parent=root;

        return;

    }

    if(z<root->elem)

        insert(root->left,z);

    else

        insert(root->right,z);

}

void createBST(BinarySearchTree *&root)

{

    int arr[]= {,,,,,,,,,};

    for(auto a:arr)

        insert(root,a);

}

//使用level记录选择v中的从哪个下标开始相加

void print(vector<int> v,int level)

{

    for(int i=level;i<v.size();++i)

        cout<<v[i]<<" ";

    cout<<endl;

}

//root开始，将当前层的值加入v中

void find_sum(BinarySearchTree *root,int sum,vector<int> v,int level)

{

    if(root==NULL)

        return;

    v.push_back(root->elem);

    int tmp=;

    for(int i=level;i>-;--i)

    {

        tmp+=v[i];

        if(tmp==sum)

            print(v,i);

    }

    //每一层将当前层的结点的值放入v中，由于不是传递的引用，所以同一层放入v中的值不会影响，从root结点开始保存每一层的

    find_sum(root->left,sum,v,level+);

    find_sum(root->right,sum,v,level+);

}

int main()

{

    BinarySearchTree *root=NULL;

    createBST(root);

    vector<int> v;

    cout<<"find sum is: "<<endl;

    find_sum(root,,v,);

    return ;

}

巴特西

careercup-树与图 4.9

最新文章

热门文章