【题目】
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如输入整数22和如下二元树
10
/ \
5 12
/ \
4 7
则打印出两条路径:10, 12和10, 5, 7。
【分析】
这是百度的一道笔试题,考查对树这种基本数据结构以及递归函数的理解。
当访问到某一结点时,把该结点添加到路径上,并累加当前结点的值。
如果当前结点为叶结点并且当前路径的和刚好等于输入的整数,则当前的路径符合要求,我们把它打印出来。
如果当前结点不是叶结点,则继续访问它的子结点。当前结点访问结束后,递归函数将自动回到父结点。
因此我们在函数退出之前要在路径上删除当前结点并减去当前结点的值,以确保返回父结点时路径刚好是根结点到父结点的路径。
我们不难看出保存路径的数据结构实际上是一个栈结构,因为路径要与递归调用状态一致,而递归调用本质就是一个压栈和出栈的过程。
【代码】
/*********************************
* 日期:2013-12-17
* 作者:SJF0115
* 题目: 二叉树中和为某一值的所有路径
* 来源:百度
* 分类:经典面试题
**********************************/
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
};
//输出路径
void PrintPath(vector<int> vec){
int len = vec.size();
for(int i = 0;i < len;i++){
if(i != len-1){
cout<<vec[i]<<"->";
}
else{
cout<<vec[i]<<endl;
}//if
}//for
}
//二叉树中和为某一值的所有路径
// root 二叉树
// s 返回的路径
void FindBinaryTreePath(TreeNode *root,int sum,int& curSum,vector<int>& vec){
if(root == NULL){
return;
}
TreeNode *cur = root;
// 入栈
vec.push_back(cur->val);
// 当前和
curSum += cur->val;
// 是否到达叶子节点
bool isLeaf = ((cur->left == NULL) && (cur->right == NULL));
// 找到一条到达叶子节点的路径
if(isLeaf && curSum == sum){
//输出
PrintPath(vec);
return;
}//if
// 左子树
if(cur->left){
FindBinaryTreePath(cur->left,sum,curSum,vec);
// 当我们访问完该节点,回到父节点
// 应该从路径中删除该节点并且从curSum中减去该节点的值
curSum -= cur->left->val;
vec.pop_back();
}
// 右子树
if(cur->right){
FindBinaryTreePath(cur->right,sum,curSum,vec);
// 当我们访问完该节点,回到父节点
// 应该从路径中删除该节点并且从curSum中减去该节点的值
curSum -= cur->right->val;
vec.pop_back();
}
}
//按先序序列创建二叉树
int CreateBTree(TreeNode* &T){
int data;
//按先序次序输入二叉树中结点的值,‘-1’表示空树
cin>>data;
if(data == -1){
T = NULL;
}
else{
//生成根结点
T = new TreeNode(data);
//构造左子树
CreateBTree(T->left);
//构造右子树
CreateBTree(T->right);
}
return 0;
}
int main(){
int curSum = 0;
vector<int> vec;
TreeNode* root(0);
CreateBTree(root);
FindBinaryTreePath(root,22,curSum,vec);
return 0;
}
测试:
10 5 4 -1 -1 7 -1 -1 12 -1 -1
输出:
10->5->7
10->12
分享到:
相关推荐
32.二叉树中和为某一值的路径1
34. 二叉树中和为某一值的路径题目描述输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。下图的二叉树有两条和为 22 的路径:10, 5
java基础面试题二叉树中和为某一值的路径本资源系百度网盘分享地址
输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。输出:[[5,4,12,1],[5,6,6,5]]private List> res =
二叉树中和为某一值的路径.md
Leetcode 面试题 34 二叉树中和为某一值的路径题目描述输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直
1.2 查找最小的k个元素 4 1.3 调整数组顺序使奇数位于偶数前面 5 1.4 找出数组中两个只出现一次的数字 5 1.5 旋转数组 7 1.6 旋转数组的最小元素 11 1.7 扑克牌的顺子 13 2 树 15 2.1 二叉树的非递归操作 15
输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 原创文章 269获赞 703访问量 3万+ 关注 私信 展开阅读全文 作者:...
面试题15:在二元树中找出和为某一值的所有路径 第11章 排序 11.1 插入排序 面试题1:编码实现直接插入排序 面试题2:编码实现希尔(Shell)排序 11.2 交换排序 面试题3:编码实现冒泡排序 面试题4:编码实现快速...
输入一颗二叉树的根节点和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。路径定义为从树的根节点开始往下已知到叶节点所经过的节点所形成的一条路径。在返回值的list中,数组长度大的数组靠前。 class ...
题目输入一颗二叉树的根节点和一个整数,按字典序打印出二叉树中结点值的和为输入整数的所有路径路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径示例
示例:给定如下二叉树,以及目标和 sum = 22,返回:* Definition for a binary tree node.vector<vector<i
二叉树面试题 树和二叉树考研试题总结
1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,多和面试官沟通,然后开始做一些整体的设计和规划。不要急于提交,自己测试几个用例避免错误...
二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py二叉树模拟器.py...
二叉树中和为某一值的路径: 输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中,...
剑指Offer(Python多种思路实现):二叉树中和为某一值的路径 面试34题: 题目:二叉树中和为某一值的路径 题:输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始...
示例:给定如下二叉树,以及目标和 sum = 22,返回:思路套用回溯算法的思路设定一个结果数组result来存储所有符合条件的路径设定一个栈stack来存储当
程序员代码面试指南-第三章二叉树[牛客试网试读版].pdf