Tree Structure
101. Symmetric Tree [x]
https://leetcode.com/problems/symmetrictree/description/
iterative
1  class Solution { 
recursive
1  class Solution { 
100. Same Tree [x]
https://leetcode.com/problems/sametree/description/
1  class Solution { 
98. Validate Binary Search Tree
 BST 条件
 left < root < right
 left and right subtree has to be valid BST
https://leetcode.com/problems/validatebinarysearchtree/description/
Recursive
1  class Solution { 
Iterative (inorder traversal)
1  public boolean isValidBST(TreeNode root) { 
Lowest Common Ancestor
235. Lowest Common Ancestor of a Binary Search Tree
 proning is possible via BST property
https://leetcode.com/problems/lowestcommonancestorofabinarysearchtree/description/
1  class Solution { 
236. Lowest Common Ancestor of a Binary Tree
 root is LCA when
left
andright
is notnull
 pass LCA up to the real root as the return value
https://leetcode.com/problems/lowestcommonancestorofabinarytree/description/
1  class Solution { 
###Follow up:
 如果输入的node不在树里面怎么办
 如果两个node是相同的怎么办
 如果有两个Thread同时访问这棵树会不会有问题？可不可以有办法不用synchronized？
Depth/Height/Path
104. Maximum Depth of Binary Tree
https://leetcode.com/problems/maximumdepthofbinarytree/description/
recursive
1  class Solution { 
iterative
Iterative approach has DFS and BFS.
DFS go through each of the leave node and update a global max
along the way.
BFS maintains a count
to record the max level when doing level order traversal, which the count
is the max depth.
111. Minimum Depth of Binary Tree
 careful to the difference from max depth above
 BFS might works better than DFS since it is looking for the first leave node
https://leetcode.com/problems/minimumdepthofbinarytree/description/
DFS recursive
1  class Solution { 
BFS iterative (preferred)
 first leave node with both
left == null
andright == null
1  class Solution { 
110. Balanced Binary Tree [x]
https://leetcode.com/problems/balancedbinarytree/description/
1  class Solution { 
112. Path Sum
https://leetcode.com/problems/pathsum/description/
 path sum requires to check if current
root
is a leaf node (import)
recursive
1  class Solution { 
iterative: preorder traversal [x]
Similar solution as yours. Your solution has changed the internal tree node value, and in production code, this may be not permitted. Followed is my solution:
1  public boolean hasPathSum(TreeNode root, int sum) { 
src: https://leetcode.com/problems/pathsum/discuss/36534/Myjavanorecursivemethod
543. Diameter of Binary Tree
 diameter is number of edges between two nodes
 passing root is NOT required
https://leetcode.com/problems/diameterofbinarytree/description/
recursive
1  class Solution { 
iterative (postorder traversal) [x]
124. Binary Tree Maximum Path Sum
https://leetcode.com/problems/binarytreemaximumpathsum/description/
 definition of path is same as lc543 Diameter of Binary Tree
 path sum return node value, hence, need to consider negative node value
1  // example for [key step] 
1  class Solution { 
Note: Iterative approach is also possible with postorder traversal but less straight forward in code aspect
Binary Search Tree (BST)
108. Convert Sorted Array to Binary Search Tree
https://leetcode.com/problems/convertsortedarraytobinarysearchtree/description/
1  class Solution { 
recursive approach:
https://leetcode.com/problems/convertsortedarraytobinarysearchtree/discuss/35218/JavaIterativeSolution/33427
230. Kth Smallest Element in a BST
https://leetcode.com/problems/kthsmallestelementinabst/description/
 method1: inorder traversal of BST returns the kth smallest with
list.get(k1)
 method2: count total of node and use binary search to locate kth element
Recurisve
1  class Solution { 
Iterative
1  class Solution { 
173. Binary Search Tree Iterator
https://leetcode.com/problems/binarysearchtreeiterator/description/
 inorder traversal for BST returns a sorted list
1  /** 
Tree Traversal
Preorder
https://leetcode.com/problems/binarytreepreordertraversal/description/
Recursive
1  public ArrayList<Integer> preorderTraversal(TreeNode root) { 
Iterative
1  public class Solution { 
Iterative w/ Guide Class
 use
Guide
class helps to improve code reusabliity and flexibility ops
should be reversely pushed into stack
1  class Solution { 
Inorder
https://leetcode.com/problems/binarytreeinordertraversal/description/
Recursive
1  public ArrayList<Integer> preorderTraversal(TreeNode root) { 
Iterative v1
1  public class Solution { 
Iterative w/ Guide Class
 use
Guide
class helps to improve code reusabliity and flexibility ops
should be reversely pushed into stack
1  class Solution { 
Postorder
https://leetcode.com/problems/binarytreepostordertraversal/description/
Recursive
1  public ArrayList<Integer> preorderTraversal(TreeNode root) { 
Iterative v1
 indeed the reverse order of levelorder traversal
 since does NOT required output to be level ordred (just single list), use stack instead
1  class Solution { 
Iterative w/ Guide Class
 use
Guide
class helps to improve code reusabliity and flexibility ops
should be reversely pushed into stack
1  class Solution { 
Levelorder
102. Binary Tree Level Order Traversal
https://leetcode.com/problems/binarytreelevelordertraversal/description/
1  public class Solution { 
DFS
DFS recursive appraoch https://leetcode.com/problems/binarytreelevelordertraversal/discuss/33445/JavaSolutionusingDFS
103. Binary Tree Zigzag Level Order Traversal
 same to level order, reverse list order on ODD level
https://leetcode.com/problems/binarytreezigzaglevelordertraversal/description/
1  public class Solution { 
Tree Reconstruction
297. Serialize and Deserialize Binary Tree
https://leetcode.com/problems/serializeanddeserializebinarytree/description/
DFS prefered (preorder traversal)
 preferred cuz less code complexity
 any one kind of traversal should work
 buildString() buildTree() method
 buildString with preorder traversal
 using StringBuilder for buildString()
 using Queue for buildTree()
 why this work? since both buildString() & buildTree() uses the same preorder traversal, which garntee the results are the same
1 

BFS w/ queue
1  public class Code { 
449. Serialize and Deserialize BST
 as compact as possible (wo/
X
or#
)  using two traverals (eg. preorder + inorder) to reconstruct
 solution 297 should also work for this porblem but less effiicent in space
One traversal (preorder + BST property)
1  preorder:  root  left subtree  right subtree  
Since it is a BST, first value larger than root belongs to right subtree. we can use this property to reconstruct BST with just single traversal
Important takehome:
 BST can be reconstructed with ONE preorder traversal + BST property
 Binary Tree required at least TWO traversals we cannot take advantage of BST property
105. Construct Binary Tree from Preorder and Inorder Traversal
1  preorder:  root  left subtree  right subtree  
https://leetcode.com/problems/constructbinarytreefrompreorderandinordertraversal/description/
Observations:
 preorder: first element of preorder is always the root of current subtree
 inorder: once root found, in
inorder
array, left ofroot
is left subtree, and right ofroot
is right subtree.
 inorder: once root found, in
 preorder: Once we know the number of elements in left subtree and right subtree, we could find the corresponding roots for left subtree and right subtree from
preorder
array.
 preorder: Once we know the number of elements in left subtree and right subtree, we could find the corresponding roots for left subtree and right subtree from
 recursively repeat step 13.
Implementations:
 the hardest part of this question is to determine what indices are needed for the helper function
inStart
andinEnd
indicates the range of current subtree ininorder
arraypStart
tells the location of the root for current subtree (preorder[pStart]
)
1  class Solution { 
106. Construct Binary Tree from Inorder and Postorder Traversal
 note:
postStart
here is acutally the last element in ordering of the subtree
1  /** 
Logs
 06/02/2018: first draft finished
 07/11/2018: revisited all questions & checked LC discussion
 11/08/2018: add DFS approach for serialize & deserialize BST
 05/11/2019: add Difference between #297 and #449 (serialize and deserialize BST & BT)
 09/08/2019: updated binary tree & BST reconstruction