LeetCode 257. 二叉樹的所有路徑 - Java

問題描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        
    }
}      

代碼示範

/**
*執行用時 : 3 ms, 在Binary Tree Paths的Java送出中擊敗了98.30% 的使用者
*記憶體消耗 : 35.8 MB, 在Binary Tree Paths的Java送出中擊敗了98.51% 的使用者
*
*/
class Solution {
    List<String> list = new ArrayList<String>();
    String str = "";
    public List<String> binaryTreePaths(TreeNode root) {
        dfs(root, str);
        return list;
    }
    public void dfs(TreeNode root, String str) {
        if(root==null) { return; }
        str += root.val;
        if(root.left != null || root.right != null) { str += "->"; } // 判斷該結點是否為根節點 若為根節點,則不添加"->",若左子樹或右子樹不為空,則添加"->"
        if(root.left == null && root.right == null) { list.add(str); } // 判斷該結點是否為根節點,是的話就将字元串添加到list集合中.
        dfs(root.left, str);
        dfs(root.right, str);
        
    }
}      

自己所寫(錯誤示範,僅供自己反思)

class Solution {
    List<String> list = new ArrayList<String>();
    public List<String> binaryTreePaths(TreeNode root) {
        if(root!=null) {
            sb.append(root.val);
            if(root.left != null || root.right != null) { sb.append("->"); }
            binaryTreePaths(root.left);
             if(root.left == null && root.right == null) {list.add(sb.toString());sb.delete(sb.length()-1,sb.length());}
          // else{ sb.delete(sb.length()-1,sb.length());}
            
           
            binaryTreePaths(root.right);
            // if(root.left == null && root.right == null) {list.add(sb.toString());sb.delete(0, sb.length());}
              //else {sb.delete(3, sb.length());}
        }
        return list;
    }
}