My Practice
  • Introduction
  • Chapter 1 Combination and Permutation
    • Summary 1: Template
    • Subsets
      • Problem 78: Subsets
      • Problem 90: Unique Subsets
    • Permutation
      • Problem 46: Permutations
      • Problem 47: Unique Permutations
      • Problem 31: Next Permutation
      • Problem: Previous Permutation
      • Problem 60: Permutation Sequence
    • Combination
      • Problem 39: Combination Sum
      • Problem 40: Combination Sum II
      • Problem 216: Combination Sum III
      • Problem 377: Combination Sum IV
      • Problem 77: Combinations
      • Problem 491: Increasing Subsequences
    • Binary Tree Path Sum
      • Problem 112: Path Sum
      • Problem 113: Path Sum II
      • Problem 437: Path Sum III
    • Problem 22: Generate Parentheses
    • Problem 51: N-Queens
      • Problem 52: N-Queens II
      • Problem 37: Sudoku Solver
    • Problem 17: Letter Combinations of a Phone Number
    • Problem 93: Restore IP Addresses
    • Problem 131: Palindrome Partitioning
    • Problem 49: Group Anagrams
    • Problem 401: Binary Watch
    • Problem 320: Generalized Abbreviation
  • Chapter 2 Binary Search & Sorted Array
    • Summary 1: Binary Search Template
    • Pow & Sqrt
      • Problem 50: Pow(x, n)
      • Problem 69: Sqrt(x)
      • Problem 231: Power of Two
      • Problem: Fast Power (LintCode)
      • Problem 372: Super Pow
      • Problem 172: Factorial Trailing Zeroes
    • Problem 34: Search for a Range
    • Problem 35: Search Insert Position
    • Problem 74: Search a 2D Matrix
    • Problem 240: Search a 2D Matrix II
    • Problem 33: Search in Rotated Sorted Array
    • Problem 81: Search in Rotated Sorted Array II
    • Problem 278: First Bad Version
    • Problem 162: Find Peak Element
    • Sorted Array
      • Problem: Partition Array (LintCode)
      • Problem 26: Remove Duplicates from Sorted Array
      • Problem 80: Remove Duplicates from Sorted Array II
      • Problem 88: Merge Sorted Array
      • Problem: Merge Two Sorted Arrays II (LintCode)
      • Problem: Recover Rotated Sorted Array (LintCode)
      • Problem: Rotate String (LintCode)
      • Problem 4: Median of Two Sorted Arrays
    • Problem 215: Kth Largest Element in an Array
    • Problem 29: Divide Two Integers
    • Problem 287: Find the Duplicate Number
    • Problem 374: Guess Number Higher or Lower
  • Chapter 3 Binary Tree
    • Basics
      • Problem 110: Balanced Binary Tree
      • Problem 98: Validate Binary Search Tree
        • Problem 230: Kth Smallest Element in a BST
        • Problem: Convert Binary Search Tree to Doubly Linked List (LintCode)
      • Problem 104: Maximum Depth of Binary Tree
      • Problem 111: Minimum Depth of Binary Tree
      • Problem 100: Same Tree
        • Problem 101: Symmetric Tree
      • Problem 450: Delete Node in a BST
    • Traversals
      • Problem 144: Binary Tree Preorder Traversal
      • Problem 94: Binary Tree Inorder Traversal
        • Problem 99: Recover Binary Search Tree
      • Problem 145: Binary Tree Postorder Traversal
      • Problem 102: Binary Tree Level Order Traversal
        • Problem 107: Binary Tree Level Order Traversal II
        • Problem 103: Binary Tree Zigzag Level Order Traversal
        • Problem 515: Find Largest Value in Each Tree Row
      • Problem 314: Binary Tree Vertical Order Traversal
      • Problem 105: Construct Binary Tree from Preorder and Inorder Traversal
      • Problem 106: Construct Binary Tree from Inorder and Postorder Traversal
      • Problem: Construct BST from given preorder traversal
      • Problem 285: Inorder Successor in BST
      • Problem 255: Verify Preorder Sequence in Binary Search Tree
    • Ancestors
      • Problem 236: Lowest Common Ancestor of a Binary Tree
      • Problem 235: Lowest Common Ancestor of a Binary Search Tree
    • Serialize and Deserialize
      • Problem 297: Serialize and Deserialize Binary Tree
      • Problem 449: Serialize and Deserialize BST
    • LinkedList 与 Binary Tree 相互转换
      • Problem 109: Convert Sorted List to Binary Search Tree
      • Problem 108: Convert Sorted Array to Binary Search Tree
      • Problem 116: Populating Next Right Pointers in Each Node
        • Problem 117: Populating Next Right Pointers in Each Node II
      • Problem 114: Flatten Binary Tree to Linked List
    • Problem: Insert Node in a Binary Search Tree (LintCode)
    • Problem: Search Range in Binary Search Tree (LintCode)
    • Problem 257: Binary Tree Paths
    • Problem 124: Binary Tree Maximum Path Sum
    • Problem 129: Sum Root to Leaf Numbers
    • Problem 173: Binary Search Tree Iterator
    • Problem 298: Binary Tree Longest Consecutive Sequence
    • Problem 199: Binary Tree Right Side View
    • Problem 250: Count Univalue Subtrees
    • Problem 96: Unique Binary Search Trees
    • Problem 95: Unique Binary Search Trees II
    • Problem 156: Binary Tree Upside Down
    • Problem 366: Find Leaves of Binary Tree
    • Problem 404: Sum of Left Leaves
    • Problem 270: Closest Binary Search Tree Value
      • Problem 272: Closest Binary Search Tree Value II
    • Problem 333: Largest BST Subtree
    • Problem 315: Count of Smaller Numbers After Self
  • Chapter 4 DFS & BFS
    • Summary 1: DFS Template
    • DFS
      • Problem 339: Nested List Weight Sum
        • Problem 364: Nested List Weight Sum II
    • Topological Sort
      • Problem 207: Course Schedule
    • Problem 133: Clone Graph
    • Problem 138: Copy List with Random Pointer
    • Problem 301: Remove Invalid Parentheses
    • Print Char Board
    • Problem 200: Number of Islands
      • Problem 305: Number of Islands II
      • Problem 463: Island Perimeter
    • Problem 127: Word Ladder
      • Problem 126: Word Ladder II
    • Topological Sort
    • Problem 332: Reconstruct Itinerary
    • Problem 290: Word Pattern
      • Problem 291: Word Pattern II
    • Problem 79: Word Search
  • Chapter 5 Linked List
    • Summary 1: Pointer and update
    • Reverse Linked List
      • Problem 206: Reverse Linked List
      • Print reverse order of a Linked List
      • Problem 92: Reverse Linked List II
      • Problem 61: Rotate List
      • Problem 143: Reorder List
      • Problem 24: Swap Nodes in Pairs
      • Problem 86: Partition List
    • Iteration
      • Problem 83: Remove Duplicates from Sorted List
      • Problem 82: Remove Duplicates from Sorted List II
      • Problem 328: Odd Even Linked List
    • Basic Operations
      • Problem 148: Sort List
      • Problem 19: Remove Nth Node From End of List
        • Problem 203: Remove Linked List Elements
      • Problem 21: Merge Two Sorted Lists
      • Problem 23: Merge k Sorted Lists
        • Problem: Merge K sorted Arrays
      • Problem 237: Delete Node in a Linked List
      • Problem 147: Insertion Sort List
    • Find Cycles
      • Problem 141: Linked List Cycle
      • Problem 142: Linked List Cycle II
    • Problem 234: Palindrome Linked List
  • Chapter 6 Dynamic Programming
    • Matrix 类型
      • Problem120: Triangle
      • Problem 62: Unique Paths
      • Problem 63: Unique Paths II
      • Problem 64: Minimum Path Sum
      • Problem 221: Maximal Square
    • Sequence 类型
      • Problem 70: Climbing Stairs
      • Problem 91: Decode Ways
      • Problem 55: Jump Game
      • Problem 139: Word Break
        • Problem 140: Word Break II
      • Problem 132: Palindrome Partitioning II
      • Problem 300: Longest Increasing Subsequence
    • Two Sequences 类型
      • Problem: Longest Common Subsequence (LintCode)
      • Problem 72: Edit Distance
    • Backpack
      • Problem: Backpack I
      • Problem: Backpack II
      • Problem: Backpack III
    • Optimal Solution
      • Problem 322: Coin Change
    • Problem 198: House Robber
      • Problem 213: House Robber II
      • Problem 337: House Robber III
    • Problem 361: Bomb Enemy
      • Calculate Crossing
    • Problem 279: Perfect Squares
    • Problem 418: Sentence Screen Fitting
    • Optimal Solution
  • Chapter 7 Graph & Search
  • Chapter 8 Data Structure
    • Stack & Queue
      • Problem 232: Implement Queue using Stacks
      • Problem 155: Min Stack
      • Problem 84: Largest Rectangle in Histogram
        • Problem 85: Maximal Rectangle
      • Problem: Construct Max Tree
      • Problem 20: Valid Parentheses
        • Problem 394: Decode String
        • Problem 439: Ternary Expression Parser
        • Problem 241: Different Ways to Add Parentheses
        • Problem 282: Expression Add Operators
    • Hash
      • Problem 146: LRU Cache
      • Problem 128: Longest Consecutive Sequence
    • Heap
      • Problem 295: Find Median from Data Stream
      • Problem 218: The Skyline Problem
    • Trie
      • Problem 208: Implement Trie (Prefix Tree)
      • Problem 211: Add and Search Word - Data structure design
      • Problem 425: Word Squares
    • Problem 341: Flatten Nested List Iterator
    • Problem 281: Zigzag Iterator
    • Problem 346: Moving Average from Data Stream
    • Problem 380: Insert Delete GetRandom O(1)
      • Problem 381: Insert Delete GetRandom O(1) - Duplicates allowed
  • Chapter 9 High Frequency
    • Single Number
      • Problem 136: Single Number
      • Problem 137: Single Number II
      • Problem 260: Single Number III
      • Problem 169: Majority Element
      • Problem 229: Majority Element II
      • Problem: Majority Number III (LintCode)
    • Buying and Selling Stock
      • Problem 121: Best Time to Buy and Sell Stock
      • Problem 122: Best Time to Buy and Sell Stock II
      • Problem 123: Best Time to Buy and Sell Stock III
      • Problem 188: Best Time to Buy and Sell Stock IV
      • Problem 309: Best Time to Buy and Sell Stock with Cooldown
    • Subarray Sum
      • Problem 53: Maximum Subarray
      • Problem: Maximum Subarray II (LintCode)
      • Problem: Maximum Subarray Difference (LintCode)
      • Problem: Maximum Subarray III (LintCode)
      • Problem: Minimum Subarray (LintCode)
      • Problem: Subarray Sum (LintCode)
      • Problem: Subarray Sum Closest (LintCode)
      • Problem 152: Maximum Product Subarray
    • Two Sum
      • Problem 1: Two Sum
      • Problem 167: Two Sum II - Input array is sorted
      • Problem 15: 3Sum
      • Problem 259: 3Sum Smaller
      • Problem 16: 3Sum Closest
      • Problem 18: 4Sum
      • Problem: k Sum (LintCode)
      • Problem 416: Partition Equal Subset Sum
        • Problem 494: Target Sum
        • Problem 473: Matchsticks to Square
    • Problem: Sort Letters by Case (LintCode)
    • Problem 75: Sort Colors
  • Post Chapter 1 String
    • Sliding Window Problems
      • Problem 438: Find All Anagrams in a String
      • Problem 76: Minimum Window Substring
      • Problem 159: Longest Substring with At Most Two Distinct Characters
      • Problem 3: Longest Substring Without Repeating Characters
      • Problem 340: Longest Substring with At Most K Distinct Characters
      • Problem 239: Sliding Window Maximum
      • Problem 187: Repeated DNA Sequences
    • Problem 345: Reverse Vowels of a String
    • Problem 344: Reverse String
    • Problem 165: Compare Version Numbers
    • Problem151: Reverse Words in a String
    • Problem 125: Valid Palindrome
    • Problem 12: Integer to Roman
    • Problem 28: Implement strStr()
    • Problem 65: Valid Number
    • Problem 38: Count and Say
    • Problem 68: Text Justification
    • Problem 58: Length of Last Word
    • Problem 5: Longest Palindromic Substring
    • Problem 71: Simplify Path
    • Problem 227: Basic Calculator II
    • Problem 383: Ransom Note
    • Problem 8: String to Integer (atoi)
    • Problem 388: Longest Absolute File Path
    • Problem 288: Unique Word Abbreviation
    • Problem 161: One Edit Distance
    • Problem 271: Encode and Decode Strings
    • Problem 299: Bulls and Cows
    • Problem 44: Wildcard Matching
    • Problem 336: Palindrome Pairs
    • Problem 179: Largest Number
    • Problem 482: License Key Formatting
  • Post Chapter 2 Math
    • Bit Manipulation
      • Problem 371: Sum of Two Integers
      • Problem 461: Hamming Distance
      • Problem 191: Number of 1 Bits
      • Problem 421: Maximum XOR of Two Numbers in an Array
      • Problem 190: Reverse Bits
      • Problem 318: Maximum Product of Word Lengths
      • Problem 751: IP to CIDR
    • Problem 7: Reverse Integer
    • Problem 66: Plus One
    • Problem 9: Palindrome Number
    • Problem 2: Add Two Numbers
    • Problem 389: Find the Difference
    • Problem 13: Roman to Integer
    • Problem 273: Integer to English Words
    • Problem 67: Add Binary
      • Problem 258: Add Digits
    • Problem 43: Multiply Strings
    • Problem 268: Missing Number
    • Problem 343: Integer Break
    • Problem 357: Count Numbers with Unique Digits
    • Problem 201: Bitwise AND of Numbers Range
    • Problem 342: Power of Four
      • Problem 326: Power of Three
    • Problem 168. Excel Sheet Column Title
      • Problem 171: Excel Sheet Column Number
    • Problem 202: Happy Number
    • line
      • Problem 149: Max Points on a Line
    • Problem 319: Bulb Switcher
    • Problem 223: Rectangle Area
    • Problem 263: Ugly Number
  • Post Chapter 3 Array
    • Problem 56: Merge Intervals
    • Problem 57: Insert Interval
    • Problem 11: Container With Most Water
      • Problem 42: Trapping Rain Water
    • Problem 14: Longest Common Prefix
    • Problem 36: Valid Sudoku
    • Problem 209: Minimum Size Subarray Sum
    • Problem 73: Set Matrix Zeroes
    • Problem 48: Rotate Image
    • Problem 54: Spiral Matrix
    • Problem 59: Spiral Matrix II
    • Problem 118: Pascal's Triangle
    • Problem 119: Pascal's Triangle II
    • Problem 189: Rotate Array
    • Problem 217: Contains Duplicate
    • Problem 219: Contains Duplicate II
    • Problem 220: Contains Duplicate III
    • Problem 311: Sparse Matrix Multiplication
      • Problem: Sparse vectors of dot product
    • Reservoir Sampling
      • Problem 398: Random Pick Index
        • Random Non-Empty Slots
      • Problem 384: Shuffle an Array
    • Problem 228: Summary Ranges
    • Problem 238: Product of Array Except Self
    • Problem 283: Move Zeroes
    • Problem 289: Game of Life
    • Problem 396: Rotate Function
    • Problem 242: Valid Anagram
    • Problem 349: Intersection of Two Arrays
      • Problem 160: Intersection of Two Linked Lists
    • Problem 350: Intersection of Two Arrays II
    • Problem 387: First Unique Character in a String
    • Problem 334: Increasing Triplet Subsequence
    • Problem 325: Maximum Size Subarray Sum Equals k
    • Problem 252: Meeting Rooms
    • Problem 253: Meeting Rooms II
    • Problem 277: Find the Celebrity
    • Problem 157: Read N Characters Given Read4
    • Problem 158: Read N Characters Given Read4 II - Call multiple times
    • Problem 163: Missing Ranges
    • Problem 360: Sort Transformed Array
    • Problem 280: Wiggle Sort
      • Problem 324: Wiggle Sort II
    • Problem 274: H-Index
    • Problem 448: Find All Numbers Disappeared in an Array
      • Problem 442: Find All Duplicates in an Array
  • Facebook
    • K closest points
    • Find all the peak and valley
    • Arithmetic operation combination
    • Task Schedule
    • Fibonacci numbers
    • LinkedList BlackBox
  • Amazon
    • Right Rotation
    • Consecutive Gray Code
    • Valid Parentheses
    • Reverse Second Half of Linked List
    • Subtree
    • Find K Nearest Point
    • Overlap Rectangle
    • Window Sum
    • GCD Greatest Common Divisor
  • All Chapters Summary
    • Two Pointers
    • Permutation and Combination
    • Basic Data Structures
    • Binary search and Divide and Conquer
    • Binary Tree
    • Linked List
    • Tree
    • Bit Manipulation
  • Core Java Interview Questions
    • Sec 1: Basics of Java Questions
    • Sec 2: OOP Concepts
    • Sec 3: Exception Handling
    • Sec 4: String Handling
    • Sec 5: Nested Classes and Interfaces
    • Sec 6: Garbage Collection and I\/O Questions
    • Sec 7: Serialization, Networking and Reflection Questions
    • Sec 8: Miscellaneous Questions
    • Sec 9: Multithreading Questions
    • Sec 10: Java Collection Questions
  • Basics of Sorting
    • Bubble Sort
    • Selection Sort
    • Insertion Sort
  • Behavior Questions
    • Introduction to yourself
    • Why change Physics to CS
    • Biggest problems in working with others
    • Project 1: Apartment Finder Website
    • Project 2: Mini UNIX Shell
    • Project 3: 911 Call Data Mining
    • Project 4: Andriod Weather Forecast App
Powered by GitBook
On this page
  • 思路
  • 易错点
  • Follow Up

Was this helpful?

  1. Chapter 3 Binary Tree

Problem 257: Binary Tree Paths

PreviousProblem: Search Range in Binary Search Tree (LintCode)NextProblem 124: Binary Tree Maximum Path Sum

Last updated 5 years ago

Was this helpful?

思路

  • 经典题目,主要在于如何设置递归的情景

/**
 * 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> rst = new ArrayList<String>();
        if (root == null) {
            return rst;
        }

        helper(root, String.valueOf(root.val), rst);
        return rst;
    }

    private void helper(TreeNode root, String path, List<String> rst) {
        if (root == null) {
            return;
        }

        if (root.left == null && root.right == null) {
            rst.add(path);
            return;
        }
        if (root.left != null) {
            helper(root.left, path + "->" + String.valueOf(root.left.val), rst);
        }
        if (root.right != null) {
            helper(root.right, path + "->" + String.valueOf(root.right.val), rst);
        }
    }
}

易错点

  1. 递归 path

    helper(root.left, path + "->" + String.valueOf(root.left.val), rst);

    这里 path 是一个变量,下一层递归的时候,作为之前的变量带入给对方

  2. 加完 path 后,记得要 return

    if (root.left == null && root.right == null) {
         rst.add(path);
         return;
    }

Follow Up

如果所有的node在一条线上,时间复杂度?

  • O(n)

如果是 full binary tree,时间复杂度?

  • 如果不优化,直接用 String 来做的话,每次相当于创建一个 String,O(n^2)

  • 如果优化的话,是O(nlogn)

https://leetcode.com/problems/binary-tree-paths/