Neetcode 150 — Trees
15 min readOct 28, 2026
最近為了練習刷題，開始寫 Neetcode 150。以下是我的刷題筆記，主要以 JAVA 來練習，分類及題目來自 Neetcode。
Note
- invert, ex第一題
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
}- depth 是 node 到 root 會經過多少 edge；height 是 node 到 leaf 會經過多少 edge
- dfs 有 preorder(v -> l -> r), inorder(l -> v -> r), postorder(1 -> r -> v)
- bfs 需要搭配 queue 來遍歷每一層
- 如果想要中途就中斷 dfs，可以回傳 -1，並且上一層判斷是 -1 就回傳, ex第四題
- binary search tree 如果用 inorder，就會是從小到大，因此在找第 kth 小的元素時，可以用 inorder，ex.第12題
- 想要 serialize binary tree，可以用 preorder 搭配 null 用 ‘#’ 來表示，ex第15題
1. Invert Binary Tree
// 1.
// 題目希望將 node 的 left 和 right 左右交換，每一層都要
// 可以用 recursion 的方式搭配 preorder 或是 postorder。
//
// 假設有 n 個 noode
// Time complexity: O(n)
// Space complexity: O(logn), worst O(n)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}2. Maximum Depth of Binary Tree
// 1.
// 題目提到要找從root可以到的最長會經過多少 node
// 可以用 postOrder + recursion
//
// 假設有 n 個 node
// Time complexity: O(n)
// Space complexity: O(logn), worst:O(n)
//
// Dry run
// root = [1,2,3,null,null,4]
// maxDepth(2)=1
// maxDepth(4)=1
// maxDepth(3)=2
// maxDepth(1)=3
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return 1 + Math.max(left, right);
}
}3. Diameter of Binary Tree
// 1.
// 題目希望計算任兩個 node 最長路徑會經過多少 edge
// 因此可以 DFS + postorder + recursive
// 從最底部的 node 計算左邊長度和右邊長度，選最長的往上傳
// 過程中紀錄 max 值
//
// 假設有 n 個 node
// Time complexity: O(n)
// Space complexity: O(logn), worst: O(n)
//
// Dry run
// root = [1,null,2,3,4,5]
// 1
// \
// 2
// / \
// 3. 4
// /
// 5
// getLength(5), max=0, return 1
// getLength(3), max=1, return 2
// getLength(4), max=1, return 1
// getLength(2), max=3, return 3
// getLength(1), max=3, return 4
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
getLength(root);
return max;
}
private int getLength(TreeNode root) {
if (root == null) {
return 0;
}
int left = getLength(root.left);
int right = getLength(root.right);
max = Math.max(max, left + right);
return Math.max(left, right) + 1;
}
}4. Balanced Binary Tree
// 1. postorder + recursive
// 題目希望查看是否是 balanced binary tree, 只要 height 最多差1
// 而 height 的定義是 edge 長度
// 可以用 postorder + recursive 比較左右的 height，並回傳max(left, right)
//
// 假設有 n 個 nodoe
// Time complexity: O(n)
// Space complexity: O(logn), worst: O(n)
//
// Dry run
// root = [1,2,3,null,null,4]
// 1
// / \
// 2. 3
// /
// 4
// getHeight(2), isbalanced=true, return 1
// getHeight(4), isbalanced=true, return 1
// getHeight(3), isBalanced=true, return 2
// getHeight(1), isBalanced=true, return 3
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private boolean isBalanced = true;
public boolean isBalanced(TreeNode root) {
getHeight(root);
return isBalanced;
}
private int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
int left = getHeight(root.left);
int right = getHeight(root.right);
if (Math.abs(left - right) > 1) {
isBalanced = false;
}
return 1 + Math.max(left, right);
}
}
// 2. postorder + recursion + more fast
// 如果是不平衡的樹，回傳 -1，如果左邊是不平衡的樹，就不用再判斷右邊
// Time complexity: O(n)
// Space complxity: O(logn), worst O(n)
class Solution {
public boolean isBalanced(TreeNode root) {
return getHeight(root) != -1;
}
private int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
int left = getHeight(root.left);
if (left == -1) {
return -1;
}
int right = getHeight(root.right);
if (right == -1) {
return -1;
}
if (Math.abs(left - right) > 1) {
return -1;
}
return 1 + Math.max(left, right);
}
}Get AShiou’s stories in your inbox
Join Medium for free to get updates from this writer.
5. Same Binary Tree
// 1.
// 可以用 preorder，先比較目前的值，然後比較左右值是否一樣，
// 缺點是在當一方是 null 時，要多比較另一方是否是 null
//
// 假設有 n 個 node
// Time complexity: O(n)
// Space complexity: O(logn), worst: O(n)
//
// Dry run
// p = [1,2,3], q = [1,2,3]
// 1(T)
// / \
// 2(T) 3(T)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
return p.val == q.val
&& isSameTree(p.left, q.left)
&& isSameTree(p.right, q.right);
}
}6. Subtree of Another Tree
// 1. preoder + recursive + isSameTree
// 遍歷整棵樹，用 preorder，
// 比較 root 是否一樣，如果一樣就用上一題 isSameTree 的方式去比較
//
// 假設 root 有 n 個 node， subRoot 有 m 個 node
// Time complexity: O(nm)
// Space complexity: O(logn+logm) -> 每一次dfs是logm，但下一次dfs又是重新
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private boolean result = false;
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
dfs(root, subRoot);
return result;
}
public void dfs(TreeNode root, TreeNode subRoot) {
if (root == null) {
return;
}
if (root.val == subRoot.val && isSameTree(root, subRoot)) {
result = true;
return;
}
dfs(root.left, subRoot);
dfs(root.right, subRoot);
}
private boolean isSameTree(TreeNode root, TreeNode subRoot) {
if (root == null && subRoot == null) {
return true;
}
if (root == null || subRoot == null) {
return false;
}
return root.val == subRoot.val
&& isSameTree(root.left, subRoot.left)
&& isSameTree(root.right, subRoot.right);
}
}
// 2. root == null 時 return
//
// 假設 root 有 n 個 node， subRoot 有 m 個 node
// Time complexity: O(nm)
// Space complexity: O(logn+logm)
//
// Dry run
// 1 2
// / \ / \
// 2 3 4 5
// / \
// 4 5
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) {
return false;
}
if (isSameTree(root, subRoot)) {
return true;
}
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
private boolean isSameTree(TreeNode root, TreeNode subRoot) {
if (root == null && subRoot == null) {
return true;
}
if (root == null || subRoot == null) {
return false;
}
return root.val == subRoot.val
&& isSameTree(root.left, subRoot.left)
&& isSameTree(root.right, subRoot.right);
}
}7. Lowest Common Ancestor in Binary Search Tree
// 1. DFS + stack
// 找 p，然後把過程中會遇到的 node 用 stack 都記下來。
// 找 q，然後把過程中會遇到的 ndoe 用 stack 都記下來。
// 然後先 pop 比較多的那邊，直到兩邊 stack 的 size 一樣，接著一起 pop 看有沒有相同。
//
// 假設 tree 有 n 個 node，找到 p 需要 logn，找到 q 需要 logn
// Time complexity: O(logn)
// Space complexity: O(logn)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
ArrayDeque<TreeNode> pStack = searchNode(root, p);
ArrayDeque<TreeNode> qStack = searchNode(root, q);
while(pStack.size() > qStack.size()) {
pStack.pop();
}
while (pStack.size() < qStack.size()) {
qStack.pop();
}
while (!pStack.isEmpty()) {
TreeNode ancestor = pStack.pop();
if (ancestor == qStack.pop()) {
return ancestor;
}
}
return null;
}
private ArrayDeque<TreeNode> searchNode(TreeNode root, TreeNode goal) {
ArrayDeque<TreeNode> stack = new ArrayDeque<>();
while (root != null) {
stack.push(root);
if (root == goal) {
break;
}
if (root.val > goal.val) {
root = root.left;
} else {
root = root.right;
}
}
return stack;
}
}
// 2. DFS + iterate
// 當 p 和 q 都在左，代表 ancestor 在左邊
// 當 p 和 q 都在右，代表 ancestor 在右邊
// 當 p 和 q 一個在左，一個在右，則 root 則是 ancestor
// 當 p 在左，q 在 root，則 q 是 ancestor
//
// Time complexity: O(logn)
// Space cmoplexity: O(1)
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (root != null) {
if (root.val > p.val && root.val > q.val) {
root = root.left;
} else if (root.val < p.val && root.val < q.val) {
root = root.right;
} else {
return root;
}
}
return null;
}
}
// 3. DFS + recursive
//
// Time complexity: O(logn)
// Space complexity: O(logn)
//
// Dry run
// 5
// / \
// 3 8
// / \ / \
// 1 4 7 9
// \
// 2
// p = 3, q = 8
// return 5
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root.val > p.val && root.val > q.val) {
return lowestCommonAncestor(root.left, p, q);
}
if (root.val < p.val && root.val < q.val) {
return lowestCommonAncestor(root.right, p, q);
}
return root;
}
}8. Binary Tree Level Order Traversal
// 1. BFS
// 可以用一個 queue 來裝當下的 node，裝好後，再從 queue 拿出那一層的 node 印出
// 並把 left 和 right 放進 queue
//
// 假設 tree 有 n 個 node
// Time complexity: O(n)
// Space complexity: O(n)
//
// Dry run
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
// queue=1, sublist=[1]
// queue=23, sublist=[2,3]
// queue=4567, sublist=[4,5,6,7]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> sublist = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
sublist.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(sublist);
}
return result;
}
}9. Binary Tree Right Side View
// 1. BFS
// 題目希望印出每一層的最右邊，可以用 BFS 的方式，把最後一個 node 印出
//
// 假設有 n 個 node
// Time complexity: O(n)
// Space complexity: O(n)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (i == size - 1) {
result.add(node.val);
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return result;
}
}10. Count Good Nodes in Binary Tree
// 1. DFS
// 可以用 DFS 的方式，把前面最大的值傳下來，如果自己比之前的要大，那自己就是 good nodes
//
// 假設有 n 個 node
// Time complexity: O(n)
// Space complexity: O(logn), worst: O(n)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int count = 0;
public int goodNodes(TreeNode root) {
dfs(root, Integer.MIN_VALUE);
return count;
}
private void dfs(TreeNode root, int max) {
if (root == null) {
return;
}
if (root.val >= max) {
count++;
max = root.val;
}
dfs(root.left, max);
dfs(root.right, max);
}
}11. Valid Binary Search Tree
// 1.
// 要用 DFS，往下傳時，都要規範最小最大值，看 node 是否在規範內
//
// 假設有 n 個 node
// Time complexity: O(n)
// Space complexity: O(logn), worst: O(n)
//
// Dry run
// 5
// / \
// 2 8
// / \ / \
// 1 3 7 9
// isInRange(5, Long.MIN_VALUE, Long.MAX_VALUE)
// isInRange(2, Long.MIN_VALUE, 5) && isInRange(8, 5, Long.MAX_VALUE)
// isInRange(1, Long.MIN_VALUE, 2) && isInRange(3, 2, 5)
// isInRange(7, 5, 8) && isInRange(9, 8, Long.MAX_VALUE)
// return true
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
return isInRange(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean isInRange(TreeNode root, long min, long max) {
if (root == null) {
return true;
}
if (min < root.val && root.val < max) {
return isInRange(root.left, min, root.val)
&& isInRange(root.right, root.val, max);
} else {
return false;
}
}
}12. Kth Smallest Integer in BST
// 1. dfs + maxHeap
// 可以把值放到 maxHeap，size 則為 kth，
// 如果 size 滿了，接下來的值比 maxHeap 最上面的值小的話，就把上面的值移除，然後加新的值
// 最後的結果會是 maxHeap 最上面的值
//
// 假設有 n 個值
// Time complexity: O(n)
// Space complexity: O(logn + k) -> recursive + heap
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
public int kthSmallest(TreeNode root, int k) {
dfs(root, k);
return maxHeap.peek();
}
private void dfs(TreeNode root, int k) {
if (root == null) {
return;
}
if (maxHeap.size() == k) {
if (maxHeap.peek() > root.val) {
maxHeap.poll();
maxHeap.add(root.val);
}
} else {
maxHeap.add(root.val);
}
dfs(root.left, k);
dfs(root.right, k);
}
}
// 2. dfs + inorder
// 可以用 inorder 的方式，這樣 data 就會是從小排到大，在遍歷過程中 count k 個，則是答案
//
// Time complexity: O(logn + k), worst: O(n)
// Space complexity: O(logn), worst: O(n)
//
// Dry run
// 4
// / \
// 3 5
// /
// 2
// k = 4
// inorder(2) -> inorder(null), count=1, return -1
// inorder(3) -> inorder(2)=-1, count=2, return -1
// inorder(4) -> inorder(3)=-1, count=3, return inorder(5) -> return 5
// inorder(5) -> inorder(null)=-1, count=4 return 5
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int count = 0;
public int kthSmallest(TreeNode root, int k) {
return inorder(root, k);
}
private int inorder(TreeNode root, int k) {
if (root == null) {
return -1;
}
int left = inorder(root.left, k);
if (left != -1) {
return left;
}
count++;
if (count == k) {
return root.val;
}
return inorder(root.right, k);
}
}13. Construct Binary Tree from Preorder and Inorder Traversal
// 1. DFS + copy array
// 題目會提供 preorder 和 inorder，要組成一個 binary tree
// preorder: val left right
// inorder: left val right
// 代表可以從 preorder 的第一個值當作 root，
// inorder 的 left 到 root 為 left，
// ex. preorder = [1,2,3,4], inorder = [2,1,3,4]
// root=1, left=2, right=3, right=4
//
// 假設 array 長度都為 n
// Time complexity: O(n), 最差 O(n^2)因為要複製 array
// Space complexity: O(logn), worst:O(n)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0) {
return null;
}
TreeNode root = new TreeNode(preorder[0]);
int i = 0;
while (preorder[0] != inorder[i]) {
i++;
}
root.left = buildTree(Arrays.copyOfRange(preorder, 1, i + 1),
Arrays.copyOfRange(inorder, 0, i));
root.right = buildTree(Arrays.copyOfRange(preorder, i + 1, preorder.length),
Arrays.copyOfRange(inorder, i + 1, inorder.length));
return root;
}
}
// 2. DFS + index
// 用 index 的方式，避免複製
//
// Time complexity: O(n), worst: O(n^2)
// Space coomplexity: O(logn), worst: O(n^2)
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, inorder, 0, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int[] inorder,
int preStart, int inLeft, int inRight) {
if (inLeft > inRight) {
return null;
}
TreeNode root = new TreeNode(preorder[preStart]);
int mid = inLeft;
while (root.val != inorder[mid]) {
mid++;
}
int leftSize = mid - inLeft;
root.left = build(preorder, inorder, preStart + 1, inLeft, mid - 1);
root.right = build(preorder, inorder, preStart + leftSize + 1, mid + 1, inRight);
return root;
}
}
// 3. DFS + hashmap
// 用 hashmap 的方式避免重複 go through left
//
// Time complexity: O(n)
// Space comoplexity: O(logn), worst: O(n)
//
// Dry run
// preorder=[2,1,3,4], inorder=[1,2,3,4]
// root | preStart | inLeft | inRight | mid | leftSize
// 2 0 0 3. 1. 1
//. 1. 1 0 0 0. 0
//. x 2 0 -1
//. x. 2 1 0
//. 3 2 2 3 2. 0
// x 3 2 1
//. 4 3 3 3 3 0
// x 4 3 2
// x 4 4 3
class Solution {
private Map<Integer, Integer> inorderMap = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
return build(preorder, inorder, 0, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int[] inorder,
int preStart, int inLeft, int inRight) {
if (inLeft > inRight) {
return null;
}
TreeNode root = new TreeNode(preorder[preStart]);
int mid = inorderMap.get(root.val);
int leftSize = mid - inLeft;
root.left = build(preorder, inorder, preStart + 1, inLeft, mid - 1);
root.right = build(preorder, inorder, preStart + leftSize + 1, mid + 1, inRight);
return root;
}
}14. Binary Tree Maximum Path Sum
// 1. DFS
// 每次都算 left + right + root, 紀錄最大值，return max(left+rooot, right+root)
// 如果 left or right 負值，丟掉不算在 left + righ + root
//
// 假設有 n 個 node
// Time cmoplexity: O(n)
// Space comoplexity: O(logn), worst:O(n)
//
// Dry run
// -15
// / \
// 10 20
// / \
// 15 5
// /
// -5
// dfs | left | right | max | return
// 10 0 0 max(10, MIN)=10 10
// -5 0 0 max(-5, 10)=10 -5
// 15 0 0 max(15, 10)=15 15
// 5 0 0 max(5, 15)=15 5
// 20 15 5 max(40, 15)=40 35
// -15 10 35 max(30, 40)=40 20
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return max;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int left = Math.max(0, dfs(root.left));
int right = Math.max(0, dfs(root.right));
max = Math.max(left + right + root.val, max);
return root.val + Math.max(left, right);
}
}15. Serialize and Deserialize Binary Tree
// 1. preorder + inorder
// 題目會提供一個 binary tree，要可以 serialize 成 string，和可以 deserialize 成 tree
// 先前的第13題，只要有 preorder 和 inorder，就可以組成 binary tree
// 第一個想法是string由preorder和inorder組成，然後deserialize就可以拆解
// 每個 node 前面可以加上,來確認數字範圍
//
// 假設有 n 個 node
// Time complexity: serialize: O(n), deserialize: O(n)
// Space complexity: serialize: O(n), deserialize: O(n)
// 2. preorder + 把 null 寫成 #
// 可以使用 preorder + 紀錄 nul，serialize 成 string
// 而在 deserialize 時，把 value 放在 queue，再慢慢組成 tree
//
// Time complexity: serialize: O(n), deserialize: O(n)
// Space complexity: serialize: O(n), deserialize: O(n)
//
// Dry run
// [1,2,3,null,null,4,5]
// serialize: 1,2,3,#,#,4,5
// deserialize: queue:[1,2,3,#,#,4,5] -> [1,2,3,null,null,4,5]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "#";
}
return root.val + "," + serialize(root.left) + "," + serialize(root.right);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Queue<String> queue = new LinkedList(Arrays.asList(data.split(",")));
return deserialize(queue);
}
private TreeNode deserialize(Queue<String> queue) {
String element = queue.poll();
if (element.equals("#")) {
return null;
}
int val = Integer.valueOf(element);
TreeNode node = new TreeNode(val);
node.left = deserialize(queue);
node.right = deserialize(queue);
return node;
}
}
