来源
公众号：人魔七七
Github地址：
https://github.com/renmoqiqi/100-Days-Of-iOS-DataStructure-Algorithm
题目大意
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"]
灵感思路
给我们一个二叉树，让我们返回所有根到叶节点的路径。我们可以采用递归的思路，不停的DFS到叶结点，如果遇到叶结点的时候，那么此时一条完整的路径已经形成，我们加上当前的叶结点后变成的完整路径放到数组中。
需要注意的是对空节点的判断，以及递归函数回溯时候对一些对象的影响。
主要代码
- (void)printPathsRecurTreeNode:(DSTreeNode *)treeNode path:(NSString *)path results:(NSMutableArray <NSString *>*)results
{
//1
if (treeNode == nil) {
return;
}
//2
if (treeNode.leftChild == nil && treeNode.rightChild == nil)
{
NSString *resultsStr = [NSString stringWithFormat:@"%@%@",path,treeNode.object];
[results addObject:resultsStr];
}
else
{
//3
if (treeNode.leftChild != nil)
{
NSString *resultsStr = [NSString stringWithFormat:@"%@%@",path,[NSString stringWithFormat:@"%@->",treeNode.object]];
[self printPathsRecurTreeNode:treeNode.leftChild path:resultsStr results:results];
}
//4
if (treeNode.rightChild != nil )
{
NSString *resultsStr = [NSString stringWithFormat:@"%@%@",path,[NSString stringWithFormat:@"%@->",treeNode.object]];
[self printPathsRecurTreeNode:treeNode.rightChild path:resultsStr results:results];
}
}
}
代码解释
- 如果节点是空则返回。
- 如果当前节点是叶子节点则把这个完整路径加到数组里。
- 如果当前节点存在左孩子节点，则继续DFS直到叶子节点。
- 如果当前节点存在右孩子节点，则继续DFS直到叶子节点。
GitHubDemo：
https://github.com/renmoqiqi/100-Days-Of-iOS-DataStructure-Algorithm/tree/master/Day16/Tree_BTPaths
