首页 » C++ » Leetcode#257. Binary Tree Paths(二叉树的所有路径)

Leetcode#257. Binary Tree Paths(二叉树的所有路径)

原文 http://blog.csdn.net/xunalove/article/details/79197834

2018-01-30 02:00:56阅读(340)

题目

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"]
题意

给你一个二叉树,输出所有的路径

题解

万能递归法

C++语言
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<string>res;
    void getPaths(TreeNode* root, string now_path)
    {
        if(root->left==NULL && root->right==NULL)//左右子树都为空,一条路径查找结束
        {
            res.push_back(now_path);
        }
        if(root->left!=NULL)//左子树不为空,先添加当前元素,再查找
        {
            getPaths(root->left, now_path + "->" + to_string(root->left->val));
        }
        if(root->right!=NULL)
        {
            getPaths(root->right, now_path + "->" + to_string(root->right->val));
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        if(root==NULL)
            return res;
        getPaths(root, to_string(root->val));
        return res;
    }
};
Python语言

写python语言时,将res怎样作为全部变量,是个问题?
网上有说放在class外面,但是放在外面会导致多次运行函数输出同一个结果,后来将全局变量变为局部变量传参进去。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def getPaths(self,root, now_path, res):
        if root.left==None and root.right==None:
            res.append(now_path)
        if root.left!=None:
            self.getPaths(root.left, now_path + "->" + str(root.left.val), res)
        if root.right!=None:
            self.getPaths(root.right, now_path + "->" + str(root.right.val), res)
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        res = []
        if root == None:
            return res
        self.getPaths(root, str(root.val),res)
        return res
Python语言

后来想起来python中有一种可以在函数中在写函数的形式—高阶函数,不懂的可以查看https://www.liaoxuefeng.com/wiki/001374738125095c955c1e6d8bb493182103fac9270762a000/001386819873910807d8c322ca74d269c9f80f747330a52000或者慕课网上有节讲python高阶函数的。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        res = []
        def getPaths(root, now_path):
            if root.left==None and root.right==None:
                res.append(now_path)
            if root.left!=None:
                getPaths(root.left, now_path + "->" + str(root.left.val))
            if root.right!=None:
                getPaths(root.right, now_path + "->" + str(root.right.val))
        if root == None:
            return res
        getPaths(root, str(root.val))
        return res

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹