leetcode 257. Binary Tree Paths 深度优先遍历DFS

约定不等于承诺〃 2022-06-08 12:50 144阅读 0赞

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