iOS数据结构与算法实战 二叉树的算法实战 Binary Tree Paths

栏目: IOS · 发布时间: 5年前

内容简介:给我们一个二叉树,让我们返回所有根到叶节点的路径。我们可以采用递归的思路,不停的DFS到叶结点,如果遇到叶结点的时候,那么此时一条完整的路径已经形成,我们加上当前的叶结点后变成的完整路径放到数组中。
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];
        }
    }
    

}
复制代码

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Java Servlet & JSP Cookbook

Java Servlet & JSP Cookbook

Bruce W. Perry / O'Reilly Media / 2003-12-1 / USD 49.99

With literally hundreds of examples and thousands of lines of code, the Java Servlet and JSP Cookbook yields tips and techniques that any Java web developer who uses JavaServer Pages or servlets will ......一起来看看 《Java Servlet & JSP Cookbook》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具