输入一颗二叉树的跟节点和一个整数打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径(紸意: 在返回值的list中,数组长度大的数组靠前)
如下图所示遍历这颗二叉树,输入整数为16一看就知道有两个路径8、7、1和8、8、0,那么怎么实現这样的自动遍历呢首先是肯定从根节点开始遍历,那么就会想到前序遍历的方式使用前序遍历一直遍历到每条路径的叶结点为止,判断该路径的和是否为输入整数值下面采用递归的方法进行阐述,先访问根节点8继续访问7,继续访问11为叶子结点,路径是8、7、1判斷为16,满足情况记录下来,下面继续丢掉前面路径中的1,访问7的右节点22为叶子结点,路径是8、7、2判断为17,不满足情况下面继续,丢掉前面路径中的2,7重新到了根节点8,访问8的右子节点8继续访问0,0是叶子结点判断为16,记录下来下面继续,丢掉路径中的0访问8嘚右子节点3,3是叶子结点路径值8、8、3,判断是19不满足情况,丢掉路径中的3、8、8完成。
丢掉1访问7的右节点2 |
丢掉2,丢掉7访问8的右节點8 |
丢掉0,访问8的右节点3 |
vector<int> tempPath;//作为一个实时遍历节点的一维容器遍历到要求的路径把值放入上面二维容器