C++刷剑指offer（面试题34. 二叉树中和为某一值的路径）【回溯】

糖逗 · 发表于 2020-4-4 12:37:57

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由糖逗于 2020-5-8 17:28 编辑

题目描述：

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

 

示例:
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:

[
   [5,4,11,2],
   [5,8,4,5]
]
 

提示：

节点总数 <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<iostream>
#include <malloc.h>
#include <vector>
#include <math.h>
#include <queue>
#include<vector>
using namespace std;

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

TreeNode* CreateTree(vector<int> input){
        TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
        for(int i = 0; i < input.size(); i++){
                res[i].val = input[i];
                res[i].left = NULL;
                res[i].right = NULL;
        }
        for(int i= 0; i < input.size(); i++){
                if(2*i+1 < input.size()){
                        res[i].left = &res[2*i+1];
                }
                if(2*i+2 < input.size()){
                        res[i].right = &res[2*i+2];
                }
                
        }
        return res;
        
}

void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
    if(root == NULL) return;
    int insert = left + (right - left) / 2;
    res[depth][insert] = root->val;
           
    middle(root->left, res, left, insert - 1, depth + 1);
    middle(root->right, res, insert + 1, right, depth + 1);
    }

int treeDepth(TreeNode* root){
    if(root == NULL || root -> val == 0) return 0;
    return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
}
      
void PrintTree(TreeNode* root) {
    int depth = treeDepth(root);
    int width = pow(2, depth) - 1;
    vector<vector<int> > res(depth, vector<int>(width, 0));
    middle(root, res, 0, width - 1, 0);
    for(int i = 0; i < res.size(); i++){
                for(int j = 0; j < res[i].size();j++){
                        if(res[i][j] == 0){
                                cout  << " ";
                        }
                        else{
                                cout << res[i][j];
                        }
                       
                }
                cout << endl;
        }
        cout << "------------------" << endl;
    }



void dfs(TreeNode* root, vector<vector<int> >& res, int sum, vector<int>& temp){
        temp.push_back(root -> val);
        if(sum == root -> val && !root->right && !root -> left){
                res.push_back(temp);
        }
        if(root -> right) dfs(root -> right, res, sum - root->val, temp);
        if(root -> left) dfs(root -> left, res, sum - root->val, temp);
        temp.pop_back();
}


vector<vector<int> > solution(TreeNode* root, int sum){
        vector<vector<int> > res;
        vector<int> temp;
        if(root == NULL) return res;
        dfs(root, res, sum, temp);
        return res;
}



int main(void){
        vector<int> input1;
        cout << "send numbers for the first tree" << endl;
        int number1;
        while(cin >> number1){
                input1.push_back(number1); 
        }
        cin.clear();
        TreeNode* root = CreateTree(input1);
        PrintTree(root);
        
        
        int sum;
        cin >> sum;
        vector<vector<int> > res = solution(root, sum);
        for(int i = 0; i < res.size(); i++){
                for(int j = 0; j < res[0].size(); j++){
                        cout << res[i][j] << " ";
                        }
                        cout << endl;
                } 
        
        return 0;
}

注意事项：
1.回溯法
2.本地调试后未输出多个方案，但leetcode上通过了。

糖逗 · 发表于 2020-4-4 12:38:40

新增代码：

void dfs(TreeNode* root, vector<vector<int> >& res, int sum, vector<int>& temp){
        temp.push_back(root -> val);
        if(sum == root -> val && !root->right && !root -> left){
                res.push_back(temp);
        }
        if(root -> right) dfs(root -> right, res, sum - root->val, temp);
        if(root -> left) dfs(root -> left, res, sum - root->val, temp);
        temp.pop_back();
}


vector<vector<int> > solution(TreeNode* root, int sum){
        vector<vector<int> > res;
        vector<int> temp;
        if(root == NULL) return res;
        dfs(root, res, sum, temp);
        return res;
}

糖逗 · 发表于 2020-4-7 15:49:20

112. 路径总和
相似题目：

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例: 
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

核心新增代码：

bool solution(TreeNode* root, int target){
        if(root == NULL) return false;
        if(target == root -> val && root -> right == NULL && root -> left == NULL) return true;
        return solution(root -> left, target - root -> val) || solution(root -> right, target - root -> val);

}

int main(void){
        cout << "please send the number for the tree" << endl;
        vector<int> input;
        int number;
        while(cin >> number){
                input.push_back(number);
        } 
        TreeNode* root = Create
        Tree(input);
        PrintTree(root);
        cin.clear();
        int target;
        cin >> target;
        
        bool res = solution(root, target);
        cout << res << endl;
        
        return 0;
}

注意要点：
1.使用了深度优先搜索。

糖逗 · 发表于 2020-4-8 14:13:19

相似题目：129. 求根到叶子节点数字之和

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

说明: 叶子节点是指没有子节点的节点。

示例 1:

输入: [1,2,3]
    1
   / \
  2   3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.
示例 2:

输入: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
输出: 1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495.
从根到叶子节点路径 4->9->1 代表数字 491.
从根到叶子节点路径 4->0 代表数字 40.
因此，数字总和 = 495 + 491 + 40 = 1026.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-root-to-leaf-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<iostream>
#include <malloc.h>
#include <vector>
#include <math.h>
#include <queue>
#include<vector>
using namespace std;

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

TreeNode* CreateTree(vector<int> input){
    TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
    for(int i = 0; i < input.size(); i++){
            res[i].val = input[i];
            res[i].left = NULL;
            res[i].right = NULL;
    }
    for(int i= 0; i < input.size(); i++){
            if(2*i+1 < input.size()){
                    res[i].left = &res[2*i+1];
            }
            if(2*i+2 < input.size()){
                    res[i].right = &res[2*i+2];
            }
           
    }
    return res;
        
}

void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
    if(root == NULL) return;
    int insert = left + (right - left) / 2;
    res[depth][insert] = root->val;
           
    middle(root->left, res, left, insert - 1, depth + 1);
    middle(root->right, res, insert + 1, right, depth + 1);
    }

int treeDepth(TreeNode* root){
    if(root == NULL || root -> val == 0) return 0;
    return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
}
      
void PrintTree(TreeNode* root) {
    int depth = treeDepth(root);
    int width = pow(2, depth) - 1;
    vector<vector<int> > res(depth, vector<int>(width, 0));
    middle(root, res, 0, width - 1, 0);
    for(int i = 0; i < res.size(); i++){
        for(int j = 0; j < res[i].size();j++){
                if(res[i][j] == 0){
                        cout  << " ";
                }
                else{
                        cout << res[i][j];
                }
               
        }
        cout << endl;
    }
    cout << "------------------" << endl;
}

void dfs(TreeNode* root, vector<int>& store, string& temp){
    temp += to_string(root -> val);
        if(root -> right == NULL && root -> left == NULL) store.push_back(atoi(temp.c_str()));
        
        if(root -> right != NULL)dfs(root -> right, store, temp);
        if(root -> left != NULL)dfs(root -> left, store, temp);
        temp.erase(temp.size()-1);

} 


int solution(TreeNode* root){
        if(root == NULL) return 0;
    vector<int> store;
    string temp;
        dfs(root, store, temp);
        int res = 0;
        for(int i = 0; i< store.size(); i++){
                res += store[i];
        } 
        return res;
}

int main(void){
        vector<int> input1;
    cout << "send numbers for the  tree" << endl;
    int number1;
    while(cin >> number1){
            input1.push_back(number1);
    }
    cin.clear();
    TreeNode* root = CreateTree(input1);
    PrintTree(root);
    
    
    int res = solution(root);
    cout << res << endl;
    return 0;
}

账号		自动登录	找回密码
密码			立即注册

[技术交流] C++刷剑指offer（面试题34. 二叉树中和为某一值的路径）【回溯】

马上注册，结交更多好友，享用更多功能^_^

本帖被以下淘专辑推荐: