leetcode-257:二叉树的所有路径

简介: leetcode-257:二叉树的所有路径

题目

题目链接

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

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

示例 1:

输入:root = [1,2,3,null,5]
输出:["1->2->5","1->3"]

示例 2:

输入:root = [1]
输出:["1"]

解答

方法一:层序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        if not root:
            return []
        paths = []
        node_queue = collections.deque([root])
        path_queue = collections.deque([str(root.val)])
        while node_queue:
            node = node_queue.popleft()
            path = path_queue.popleft()
            if not node.left and not node.right:
                paths.append(path)
            if node.left:
                node_queue.append(node.left)
                path_queue.append(path+'->'+str(node.left.val))
            if node.right:
                node_queue.append(node.right)
                path_queue.append(path+'->'+str(node.right.val))
        return paths

c++写法

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        if(!root) return {};
        queue<TreeNode*> queue_node;
        queue<string> queue_path;
        queue_node.push(root);
        queue_path.push(to_string(root->val));
        vector<string> res;
        while(!queue_node.empty()){
            TreeNode* cur=queue_node.front();
            queue_node.pop();
            string path=queue_path.front();
            queue_path.pop();
            if(!(cur->left||cur->right)) res.push_back(path);
            if(cur->left){
                queue_node.push(cur->left);
                queue_path.push(path+"->"+to_string(cur->left->val));
            }
            if(cur->right){
                queue_node.push(cur->right);
                queue_path.push(path+"->"+to_string(cur->right->val));
            }
        }
        return res;
    }   
};

c++精简的写法

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        queue<pair<TreeNode*,string>> q;
        q.push({root,to_string(root->val)});
        while(!q.empty()){
            auto [cur,str]=q.front();
            q.pop();
            if(!(cur->left||cur->right)){
                res.push_back(str);
            }
            if(cur->left){
                q.push({cur->left,str+"->"+to_string(cur->left->val)});
            }
            if(cur->right){
                q.push({cur->right,str+"->"+to_string(cur->right->val)});
            }
        }
        return res;
    }
};     

java写法

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res=new LinkedList<>();
        Queue<TreeNode> q1=new LinkedList<>();
        Queue<String> q2=new LinkedList<>();
        q1.add(root);
        q2.add(String.valueOf(root.val));
        while(!q1.isEmpty()){
            TreeNode cur=q1.poll();
            String curPath=q2.poll();
            if(cur.left==null&&cur.right==null){
                res.add(curPath);
            }
            if(cur.left!=null){
                q1.add(cur.left);
                q2.add(curPath+"->"+String.valueOf(cur.left.val));
            }
            if(cur.right!=null){
                q1.add(cur.right);
                q2.add(curPath+"->"+String.valueOf(cur.right.val));
            }
        }
        return res;
    }
}


目录
打赏
0
0
0
0
7
分享
相关文章
|
2月前
【LeetCode 35】112.路径总和
【LeetCode 35】112.路径总和
28 0
|
2月前
【LeetCode 36】113.路径总和II
【LeetCode 36】113.路径总和II
32 0
|
2月前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
27 2
|
2月前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
20 2
|
2月前
【LeetCode 28】102.二叉树的层序遍历
【LeetCode 28】102.二叉树的层序遍历
19 2
|
2月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
22 0
|
2月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
20 0
|
2月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
25 0
|
2月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
23 0
|
2月前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
19 0
AI助理

阿里云 AI 助理已上线!

快来体验一下吧。