在二元树中找出和为某一值的所有路径 | 微软经典面试题解析


---答题基础知识储备---

树操作中“广度优先遍历”与“深度优先遍历”的区别

  1. 二叉树深度优先遍历非递归的通用做法是使用栈,广度优先遍历非递归的通用做法是使用线性表。

  2. 树的深度优先遍历原理是对每一个可能的分支路径深入到不能在深入为止,而且每个节点只访问一次,需要特别注意的是,二叉树的深度优先遍历可以细分为先序遍历、中序遍历和后序遍历三种;
    树的广度优先遍历又叫做层次优先遍历,原理是对树由上至下逐层进行访问,在每一层中由左至右,访问完一层再访问下一层,直到访问完所有节点。

  3. 深度优先搜索算法:操作栈中不保留树的全部节点,只保留当前路径上的节点,占用空间小;可以回溯(通过入栈、出栈操作);运行速度较慢;

    广度优先搜索算法:操作线性表中保存全部节点,占用空间较大,在遇到广度优先的问题时,注意考虑内存溢出和节省内存空间的问题;不可以回溯;运行速度较快;

------

题目:

输入一个整数和一棵二元树,从树的根节点开始向下访问,一直到叶节点所经过的所有节点形成一条路径;要求打印出和与输入整数相等的所有路径。

例如,输入整数22和如下二元树:

    10

   / \

  5  12

 / \

4   7

则结果会打印出两条路径:10,5,7和10,12

二元树节点的数据结构定义为:

struct BinaryTreeNode // a node in the binary tree  
{  
    int m_nValue; // value of node  
    BinaryTreeNode *m_pLeft; // left child of node  
    BinaryTreeNode *m_pRight; // right child of node  
};


答题分析:

使用递归方式对二元树进行深度优先前序遍历,使用堆栈保存当前经过的路径;

  1. 设置一个变量sum保存当前路径经过节点值的和

  2. 对于非叶子节点,将当前节点值加入sum,继续向下遍历

  3. 对于叶子节点,将当前节点值加入sum,并比较sum和预设值

    如果sum==预设值,返回true及当前压入栈的路径,删除当前节点

    如果sum!=预设值,删除当前节点,sum值减去当前节点值,向上回溯,继续遍历

  4. 对于被删除的节点,直接返回false


解答:

代码实现:

struct TreeNode{
    int data;
    TreeNode * left;
    TreeNode * right;
};
void printPaths(TreeNode * root,int sum){
    int path[MAX_HEIGHT];
    helper(root,sum,path,0);
}
void helper(TreeNode * root,int sum,int path[],int top){
     path[top++] = root.data;
     sum -= root.data;
     if(root->left==NULL&&root->right==NULL){
         // 叶子节点
         if(sum==0) printPath(path,top);
     }else{
         // 非叶子节点  继续向下遍历
         if(root->left!=NULL) helper(root->left,sum,path,top);
         if(root->right!=NULL) helper(root->right,sum,path,top);
     }
     top--;// 回溯
     sum += root.data;
}


本文发表于2017年10月28日 16:33
阅读 2718 讨论 1 喜欢 2

讨论

周娱

君子和而不同
按照自己的方式,去度过人生

4970 1346987
抢先体验

扫码体验
趣味小程序
文字表情生成器

加入组织

扫码添加周娱微信
备注“加入组织”
邀请进开发群

闪念胶囊

让一个团队走向平庸的最佳方式,是让成员们持续地干那些不让他们感到自豪的事情。

最近1 2年发现成长的最好方式是研究开源的项目,自己实践。成长速度非常的快,一个好的项目需要考虑的细节很多。

不积跬步无以至千里,越焦虑越要扎实干。

不要试图鹤立鸡群,趁早离开那群鸡!

程序员过节需要的不是美女、不是美食、不是不加班!他们需要的是写代码,一群人写、往死里写、通宵写!!那种暗流涌动的狂欢,远比虚无庸俗的食色更让他们振奋!! by芋头

面试的时候,常常会问数组和链表的区别,很多人都回答说,“链表适合插入、删除,时间复杂度 O(1);数组适合查找,查找时间复杂度为 O(1)”。 实际上,这种表述是不准确的。数组是适合查找操作,但是查找的时间复杂度并不为 O(1)。即便是排好序的数组,你用二分查找,时间复杂度也是 O(logn)。 所以,正确的表述应该是,数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)。

找一个bug就好比从一泡烂泥里找一条泥鳅,写一个bug就好比往一泡烂泥里丢一条泥鳅进去

数据结构在某种程度上和设计模式类似,都是前辈的武功套路。不同的是,设计模式是近几十年的卓越程序员的智慧结晶,而数据结构是几百上千年的无数科学家、数学家的智慧沉淀,更加具有深厚的背景。

18年元旦立下的flag要集中突击一下了.....

Copyright © 2016 - 2018 Cion.
All Rights Reserved.
备案:鲁ICP备16007319号.