CS
Algorithm
Algorithmmaster
Algorithm
Algorithmmaster
  • lintcode
  • EPI
    • String
      • Base Convert
  • Graph
    • Inorder Successor in BST
    • Balanced Binary Tree
    • All Paths From Source to Target
  • LinkedIn
    • House robber II
    • Single Number
    • Flatten Binary Tree to Linked List
    • Smallest Difference pair of values between two unsorted Arrays
    • Word Search II
    • Implement Trie (Prefix Tree)
    • K Closest Points
    • implement BST
    • HashMap
    • Implement strStr()
    • Min Stack
    • Meeting Rooms
    • Shortest Completing Word
    • Longest Palindromic Substring
    • Longest Palindromic Subsequence
    • Count Different Palindromic Subsequences
    • Palindromic Substrings
    • Sparse Matrix Multiplication
    • Insert Delete GetRandom O(1) - Duplicates allowed
    • Bulb Switcher
    • Verify Preorder Sequence in Binary Search Tree
    • Untitled
    • Find the Celebrity
    • Coin Change
    • Partition Equal Subset Sum
    • Permutation Sequence
    • Next Permutation
    • Kth Smallest Element in a BST
    • Word Search
    • Word Break
    • Shuffle an Array
    • Add Two Numbers
    • Longest Substring Without Repeating Characters
    • Longest Increasing Subsequence
    • 3Sum Smaller
    • LFU Cache
    • Copy List with Random Pointer
    • Linked List Cycle
    • Merge Sorted Array
    • Two Sum II - Input array is sorted
    • Search Insert Position
    • Find First and Last Position of Element in Sorted Array
    • Combination Sum
    • Path Sum
    • Roman to Integer
    • Valid Parentheses
    • Product of Array Except Self
    • Permutations
    • 3Sum
    • Reverse Integer
    • Longest Common Subsequence and substring
    • Implement Stack using Queues
    • Sort Characters By Frequency
    • Delete Node in a BST
    • Invert Binary Tree
    • Serialize and Deserialize BST
    • Reverse String
    • Binary Tree Zigzag Level Order Traversal
    • Friend Circles
    • Letter Combinations of a Phone Number
    • Fizz Buzz
    • Encode and Decode TinyURL
    • Binary Tree Right Side View
    • Shortest Word Distance III
    • Binary Search Tree Iterator
    • Kth Largest Element in an Array
    • Clone Graph
    • Lowest Common Ancestor III
    • Lowest Common Ancestor II
    • Reverse Words in a String
    • Path Sum
    • Find K Pairs with Smallest Sums
    • Validate Binary Search Tree
    • All O`one Data Structure
    • Top K Frequent Elements
    • Integer to Roman
    • Shortest Word Distance III
    • Edit Distance
    • Profitable Schemes
    • Minimum Window Substring
    • LRU Cache
    • Text Justification
    • Integer to English Words
    • Partition to K Equal Sum Subsets
    • Graph Valid Tree
    • Exclusive Time of Functions
    • Repeated DNA Sequences
    • Valid Number
    • Insert Delete GetRandom O(1)
    • Same Tree
    • Friends Within Three Jumps
    • Isomorphic Strings
    • Sum of Square Numbers
    • Valid Perfect Square
    • Evaluate Reverse Polish Notation
    • House Robber
    • Palindromic Substrings
    • Find Largest Value in Each Tree Row
    • Can Place Flowers
    • Insert Interval
    • Maximum Depth of Binary Tree
    • Two Sum
    • Paint House II
    • Max Points on a Line
    • Word Ladder II
    • Word Ladder
    • Validate IP Address
    • Maximum Product Subarray
    • Factor Combinations
    • Flatten Nested List Iterator
    • Max Stack
    • Number of Connected Components in an Undirected Graph
    • Combination Sum II
    • Permutations II
    • Permutations
    • Climbing Stairs
    • Paint House
    • Closest Binary Search Tree Value
    • Closest Binary Search Tree Value II
    • Rotate String
    • Max Area of Island
    • Maximum Subarray
    • Serialize and Deserialize Binary Tree
    • Second Minimum Node In a Binary Tree
    • Lowest Common Ancestor of a Binary Tree
    • Lowest Common Ancestor of a Binary Search Tree
    • Symmetric Tree
    • Binary Tree Upside Down
    • Maximum Depth of Binary Tree
    • Find Leaves of Binary Tree
    • Number of Islands
    • Nested List Weight Sum II
    • Nested List Weight Sum
    • Merge Intervals
    • Valid Triangle Number
    • Find K Closest Elements
    • Find Smallest Letter Greater Than Target
    • Pow(x,n)
    • Search in Rotated Sorted Array II
    • Search in Rotated Sorted Array
    • Sqrt(x)
    • Intersection of Two Linked Lists
    • Binary Tree Level Order Traversal
    • Shortest Word Distance
    • Two Sum III - Data structure design
    • Shortest Word Distance II
  • Binary Search
    • Find K Closest Elements
    • Find Min In Rotated Sorted Array
    • Find Peak Element
    • First Bad Version
    • First Position Of Target
    • Guess Num Higer Or Lower
    • Last Position Of Target
    • Longest Increasing Subsequence
    • Russian Doll Envelopes
    • Search In Big Sorted Array
    • Search Insert Position
    • Single Number IV
    • pow(x,n)
    • sqrt
    • Search in Rotated Sorted Array
    • Search in Rotated Sorted Array II
    • Find Minimum in Rotated Sorted Array
    • Find Minimum in Rotated Sorted Array II
    • Search for a Range
    • Intersection of Two Arrays
    • Count of Smaller Numbers After Self
  • Binary Tree
    • 107. Binary Tree Level Order Traversal II
    • Lowest Common Ancestor of a Binary Tree
    • Lowest Common Ancestor of a Binary Tree II
    • Lowest Common Ancestor III
    • preorder Traversal
    • Inorder traversal
    • Binary Tree Path
    • post Order traversal
    • Level Traversal
    • Serialize and Deserialize Binary Tree 07/25
    • Find Leaves of Binary Tree 07/25
    • Sum of Left Leaves 07/25
    • Recover Binary Search Tree 07/26
    • Check Full Binary Tree 07/26
    • Binary Tree Longest Consecutive Sequence07/26
    • Equal Tree Partition 07/27
    • Same Tree 07/27
    • Sum Root to Leaf Numbers 07/26
    • Binary Search Tree Iterator 07/28
    • Preorder morris traversal 07/29
    • inorder traversal morris 07/29
  • BFS
    • Search Graph Nodes 07/30
    • Is Graph Bipartite? 07/30
    • Walls and Gates 07/30
    • Clone Graph 07/30
    • Word Ladder 07/30
    • Topological Sorting 08/01
    • Course Schedule 08/03
    • Course Schedule II 08/04
  • DFS
    • Target Sum 08/06
    • Minimum Subtree 08/07
    • Word Search 08/07
    • Pacific Atlantic Water Flow 08/08
    • Matrix Water Injection 08/10
    • Maximum Subtree 08/10
  • Dynamic Programming
    • 931. Minimum Falling Path Sum
    • Unique Binary Search Trees
  • Linked List
    • Reverse Linked List
    • Linked List Cycle
    • Swap Nodes in Pairs
    • Odd Even Linked List
    • Merge k Sorted Lists
    • Partition List
    • Palindrome Linked List
    • Reorder List
    • Linked List Cycle II
    • Delete Node in a Linked List
    • Reverse Nodes in k-Group
    • Rotate List
    • Reverse Linked List II
  • Arrays
    • 189. Rotate Array
    • 80. Remove Duplicates from Sorted Array II
    • 26. Remove Duplicates from Sorted Array
    • 628. Maximum Product of Three Numbers
    • 48. Rotate Image
    • 289. Game of Life
    • 334. Increasing Triplet Subsequence
    • 11. Container With Most Water
    • 122.Best Time to Buy and Sell Stock II
    • 274. H-Index
    • 134. Gas Station
    • 118. Pascal's Triangle
    • Sort Colors
    • Remove Element
    • Merge sorted array
    • First Missing Positive
  • Strings
    • 93. Restore IP Addresses
    • 71. Simplify Path
    • 43. Multiply Strings
    • 606. Construct String from Binary Tree
    • 917. Reverse Only Letters
    • 929.Unique Email Addresses
    • Valid Anagram
    • Compare Strings
    • Anagrams
    • Longest Common Prefix
    • Implement strStr()
    • String to Integer (atoi)
Powered by GitBook
On this page

DFS

PreviousCourse Schedule II 08/04NextTarget Sum 08/06

Last updated 6 years ago

遇到找所有方案的题，一定是DFS，90%DFS的题，要么是排列 要么是组合

组合搜索问题 问题模型：求出所有满足条件的组合 判断条件：组合中的元素是顺序无关的 时间复杂度：与2^n有关

如果面试官不要求，DFS的题都可以用递归来做，那么递归的三要素是： 1. 递归的定义 2. 递归的拆解 3. 递归的出口

排列搜索问题： 问题模型：给出所有满足条件的排列 判断条件：组合中的元素是顺序相关的 时间复杂度：与n！有关

通用的DFS 时间复杂度计算公式： O(答案个数*构造每个答案的时间)

必背程序： Tree traversal Combination Permutation

http://www.jiuzhang.com/solutions/binary-tree-preorder-traversal/
http://www.jiuzhang.com/solutions/binary-tree-inorder-traversal/
http://www.jiuzhang.com/solutions/binary-tree-postorder-traversal/
http://www.jiuzhang.com/solutions/binary-search-tree-iterator/
http://www.jiuzhang.com/solutions/subsets/
http://www.jiuzhang.com/solutions/permutations/