二叉树——257. 二叉树的所有路径

古城微笑少年丶 2023-10-08 16:12 25阅读 0赞

## 1 题目描述 ##

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

## 2 题目示例 ##

![在这里插入图片描述][f6a963ea9776482daf98dc2b60b8740e.png]  
示例 2：

输入：root = \[1\]  
输出：\[“1”\]

## 3 题目提示 ##

树中节点的数目在范围 \[1, 100\] 内  
\-100 <= Node.val <= 100

## 4 思路 ##

**方法一:深度优先搜索**  
最直观的方法是使用深度优先搜索。在深度优先搜索遍历二叉树时，我们需要考虑当前的节点以及它的孩子节点。  
如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子节点。  
如果当前节点是叶子节点，则在当前路径末尾添加该节点后我们就得到了—条从根节点到叶子节点的路径，将该路径加入到答案即可。  
如此，当遍历完整棵二叉树以后我们就得到了所有从根节点到叶子节点的路径。当然，深度优先搜索也可以使用非递归的方式实现，这里不再整述。  
**复杂度分析**  
·时间复杂度:o(N²)，其中N表示节点数目。在深度优先搜索中每个节点会被访问一次且只会被访问一次，每一次会对path变量进行拷贝构造，时间代价为O(N)，故时间复杂度为O(N²)。  
空间复杂度:o(N²)，其中N表示节点数目。除答案数组外我们需要考虑递归调用的栈空间。在最坏情况下，当二叉树中每个节点只有一个孩子节点时，即整棵二叉树呈—个链状，此时递归的层数为N，此时每一层的path变量的空间代价的总和为![在这里插入图片描述][f347708f4fad4ccd9ca2b64883813dce.png]

空间复杂度为o(N²)。最好情况下，当二叉树为平衡二叉树时，它的高度为log N，此时空间复杂度为O((log N)²)。

**方法二:广度优先搜索**  
我们也可以用广度优先搜索来实现。我们维护—个队列，存储节点以及根到该节点的路径。一开始这个队列里只有根节点。在每一步迭代中，我们取出队列中的首节点，如果它是叶子节点，则将它对应的路径加入到答案中。如果它不是叶子节点，则将它的所有孩子节点加入到队列的末尾。当队列为空时广度优先搜索结束，我们即能得到答案。  
复杂度分析  
·时间复杂度:o(N²)，其中N表示节点数目。分析同方法  
一。  
·空间复杂度:o(N²)，其中N表示节点数目。在最坏情况下，队列中会存在N个节点，保存字符串的队列中每个节点的最大长度为N，故空间复杂度为o(N²)。

## 5 我的答案 ##

深度优先搜索：

class Solution {
        
        public List<String> binaryTreePaths(TreeNode root) {
        
            List<String> paths = new ArrayList<String>();
            constructPaths(root, "", paths);
            return paths;
        }
    
        public void constructPaths(TreeNode root, String path, List<String> paths) {
        
            if (root != null) {
        
                StringBuffer pathSB = new StringBuffer(path);
                pathSB.append(Integer.toString(root.val));
                if (root.left == null && root.right == null) {
          // 当前节点是叶子节点
                    paths.add(pathSB.toString());  // 把路径加入到答案中
                } else {
        
                    pathSB.append("->");  // 当前节点不是叶子节点，继续递归遍历
                    constructPaths(root.left, pathSB.toString(), paths);
                    constructPaths(root.right, pathSB.toString(), paths);
                }
            }
        }
    }

广度优先：

class Solution {
        
        public List<String> binaryTreePaths(TreeNode root) {
        
            List<String> paths = new ArrayList<String>();
            if (root == null) {
        
                return paths;
            }
            Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
            Queue<String> pathQueue = new LinkedList<String>();
    
            nodeQueue.offer(root);
            pathQueue.offer(Integer.toString(root.val));
    
            while (!nodeQueue.isEmpty()) {
        
                TreeNode node = nodeQueue.poll(); 
                String path = pathQueue.poll();
    
                if (node.left == null && node.right == null) {
        
                    paths.add(path);
                } else {
        
                    if (node.left != null) {
        
                        nodeQueue.offer(node.left);
                        pathQueue.offer(new StringBuffer(path).append("->").append(node.left.val).toString());
                    }
    
                    if (node.right != null) {
        
                        nodeQueue.offer(node.right);
                        pathQueue.offer(new StringBuffer(path).append("->").append(node.right.val).toString());
                    }
                }
            }
            return paths;
        }
    }

给一下C++的答案：

class Solution {
        
    public:
        void construct_paths(TreeNode* root, string path, vector<string>& paths) {
        
            if (root != nullptr) {
        
                path += to_string(root->val);
                if (root->left == nullptr && root->right == nullptr) {
          // 当前节点是叶子节点
                    paths.push_back(path);                              // 把路径加入到答案中
                } else {
        
                    path += "->";  // 当前节点不是叶子节点，继续递归遍历
                    construct_paths(root->left, path, paths);
                    construct_paths(root->right, path, paths);
                }
            }
        }
    
        vector<string> binaryTreePaths(TreeNode* root) {
        
            vector<string> paths;
            construct_paths(root, "", paths);
            return paths;
        }
    };

class Solution {
        
    public:
        vector<string> binaryTreePaths(TreeNode* root) {
        
            vector<string> paths;
            if (root == nullptr) {
        
                return paths;
            }
            queue<TreeNode*> node_queue;
            queue<string> path_queue;
    
            node_queue.push(root);
            path_queue.push(to_string(root->val));
    
            while (!node_queue.empty()) {
        
                TreeNode* node = node_queue.front(); 
                string path = path_queue.front();
                node_queue.pop();
                path_queue.pop();
    
                if (node->left == nullptr && node->right == nullptr) {
        
                    paths.push_back(path);
                } else {
        
                    if (node->left != nullptr) {
        
                        node_queue.push(node->left);
                        path_queue.push(path + "->" + to_string(node->left->val));
                    }
    
                    if (node->right != nullptr) {
        
                        node_queue.push(node->right);
                        path_queue.push(path + "->" + to_string(node->right->val));
                    }
                }
            }
            return paths;
        }
    };

[f6a963ea9776482daf98dc2b60b8740e.png]: https://img-blog.csdnimg.cn/f6a963ea9776482daf98dc2b60b8740e.png
[f347708f4fad4ccd9ca2b64883813dce.png]: https://img-blog.csdnimg.cn/f347708f4fad4ccd9ca2b64883813dce.png