题目
给你一个二叉树的根节点 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; } }