题目

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

1 / \ 2 3 \ 5

All root-to-leaf paths are:

["1->2->5", "1->3"]

https://leetcode.com/problems/binary-tree-paths/?tab=Description

思路

题目需要在找到每一个叶节点的时候记录从根到它的路径，叶节点很容易找到并并确定，难点是找到的同时得到路径。 思路是从根出发并遍历节点的时候一直记录路径，并加上递归的思想。一开始想过用一个堆栈保存路径，走到叶节点把完整路径放进结果后，回退到时把回退的路径弹出，但后面发现有更简单直接的实现方式。即一路保存路径，当发现叶节点时把路径放入结果中；当不是叶节点时，对其所有孩子节点递归调用搜索函数，并把路径放在函数参数中，使得各个递归调用的子函数都有各自独立的路径，最终能放入结果中。

源程序

class Solution { public: vector<string> binaryTreePaths(TreeNode* root) { vector<string> res; if(root) dfs(res,"",root); return res; } void dfs(vector<string> &res,string path,TreeNode* root){ path += to_string(root->val); if(root->left == NULL && root->right == NULL) res.push_back(path); else if(root->left != NULL) dfs(res,path + "->",root->left); if(root->right != NULL) dfs(res,path + "->",root->right); } };