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];
        }
    }
    

}
复制代码

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

查看所有标签

猜你喜欢:

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

从问题到程序

从问题到程序

裘宗燕 / 机械工业出版社 / 2005-9-1 / 36.00元

本书以C作为讨论程序设计的语言,讨论了基本程序设计的各方面问题。书中给出程序实例时没有采用常见的提出问题,给出解答,再加些解释的简单三步形式,而是增加了许多问题的分析和讨论,以帮助读者认识程序设计过程的实质,理解从问题到程序的思考过程。书中还尽可能详尽地解释了许多与C语言和程序设计有关的问题。 本书适合作为高等院校计算机及相关专业的教材,也可供其他学习C程序设计语言的读者阅读。一起来看看 《从问题到程序》 这本书的介绍吧!

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

html转js在线工具
html转js在线工具

html转js在线工具

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

RGB CMYK 互转工具