leetcode 257. Binary Tree Paths 深度优先遍历DFS-蒲公英云

leetcode 257. Binary Tree Paths 深度优先遍历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深度优先遍历即可。

代码如下：

import java.util.ArrayList;
import java.util.List;
/*class TreeNode
{
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
}*/
/*
 * 这道题其实很简单，但是要注意递归开始的起点和终点
 * Java中使用StringBuilder会更快点
 * */
public class Solution 
{
    List<String> res=new ArrayList<String>();
    public List<String> binaryTreePaths(TreeNode root)
    {
        if(root==null)
            return res;
        //getAllPath(root,root.val+"");
        List<Integer> one=new ArrayList<>();
        one.add(root.val);
        getAllPath(root, one);
        return res;
    }
    private void getAllPath(TreeNode root, List<Integer> one)
    {
        if(root.left==null && root.right==null)
        {
            if(one.size()==1)
                res.add(one.get(0)+"");
            else 
            {
                StringBuilder lastBuilder=new StringBuilder();
                lastBuilder.append(one.get(0));
                for(int i=1;i<one.size();i++)
                    lastBuilder.append("->"+one.get(i));
                res.add(lastBuilder.toString());
            }
        }
        if(root.left!=null)
        {   
            one.add(root.left.val);
            getAllPath(root.left, one);
            one.remove(one.size()-1);
        }   
        if(root.right!=null)
        {   
            one.add(root.right.val);
            getAllPath(root.right, one);
            one.remove(one.size()-1);
        }
    }
    private void getAllPath(TreeNode root, String path)
    {
        if(root.left==null && root.right==null)
            res.add(path);
        if(root.left!=null)
            getAllPath(root.left, path+"->"+root.left.val);
        if(root.right!=null)
            getAllPath(root.right, path+"->"+root.right.val);
    }
}

下面是C++的做法，就是做一个简单的DFS深度优先遍历，代码如下：

#include <iostream>
#include <vector>
#include <string>
using namespace std;
/*
struct TreeNode 
{
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
*/
class Solution 
{
public:
    vector<string> res;
    vector<string> binaryTreePaths(TreeNode* root) 
    {
        if (root == NULL)
            return res;
        getAll(root, to_string(root->val));
        return res;
    }
    void getAll(TreeNode* root, string one)
    {
        if (root->left == NULL && root->right == NULL)
            res.push_back(one);
        if (root->left != NULL)
            getAll(root->left, one + "->" + to_string(root->left->val));
        if (root->right != NULL)
            getAll(root->right, one + "->" + to_string(root->right->val));
    }
};