首页 > 代码库 > 重做257. Binary Tree Paths
重做257. Binary Tree Paths
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"]
Solution1: 用string是最方便的。因为string是immutable的，所以当返回的时候不会带回最后加的string。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> res=new ArrayList<String>(); dps(root,res,""); return res; } public void dps(TreeNode root, List<String> res, String sb) { if(root==null) { return; } if(root.left==null&&root.right==null) { sb+=root.val; res.add(sb); return; } dps(root.left,res,sb+root.val+"->"); dps(root.right,res,sb+root.val+"->"); } }
Solution2:
理解3种遍历tree的方式
Pre-order[edit]
- Check if the current node is empty / null
- Display the data part of the root (or current node).
- Traverse the left subtree by recursively calling the pre-order function.
- Traverse the right subtree by recursively calling the pre-order function.
In-order[edit]
- Check if the current node is empty / null
- Traverse the left subtree by recursively calling the in-order function.
- Display the data part of the root (or current node).
- Traverse the right subtree by recursively calling the in-order function.
In a search tree, in-order traversal retrieves data in sorted order.[4]
Post-order[edit]
- Check if the current node is empty / null
- Traverse the left subtree by recursively calling the post-order function.
- Traverse the right subtree by recursively calling the post-order function.
- Display the data part of the root (or current node).
这个方法用的是先序遍历。1.先检查是不是null，是不是leaf。也就是检查返回点／回溯点。 2.对root操作 3.遍历左子树 4.遍历右子树。
因为用的是stringbuilder是mutable的。所以在返回的时候要返回到之前节点的长度。也就是root的长度。所以在对root操作的时候要记录root时候stringbuilder的length.可以验证一下：null节点的root node也就是之前的长度。leaf node root node也就是上一个node长度。因此在回溯的时候要分别重新set length。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> res=new ArrayList<String>(); StringBuilder save=new StringBuilder(); dps(root,res,save); return res; } public void dps(TreeNode root, List<String> res, StringBuilder sb) { if(root==null) { return; } if(root.left==null&&root.right==null) { sb.append(root.val); res.add(sb.toString()); return; } sb.append(root.val); sb.append("->"); int length=sb.length(); dps(root.left,res,sb); sb.setLength(length); dps(root.right,res,sb); sb.setLength(length); } }
重做257. Binary Tree Paths
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。