\chapter{Tree}

\subsubsection{500以上的题目暂时未录入}

\section{Maximum Depth of Binary Tree} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

\subsubsection{Solution}

\begin{Code}

private int maxDepth(TreeNode node) {

if (node == null) {

return 0;

}

return Math.max(maxDepth(node.left), maxDepth(node.right)) + 1;

}

\end{Code}

\section{Invert Binary Tree} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

Invert a binary tree.

\begin{Code}

4 4

/ \ / \

2 7 to 7 2

/ \ / \ / \ / \

1 3 6 9 9 6 3 1

\end{Code}

\subsubsection{Solution I}

\begin{Code}

public TreeNode invertTree(TreeNode root) {

if (root == null) {

return null;

}

TreeNode right = root.right;

root.right = invertTree(root.left);

root.left = invertTree(right);

return root;

}

\end{Code}

\subsubsection{Solution II}

\begin{Code}

public TreeNode invertTree(TreeNode root) {

if (root == null) {

return null;

}

Queue<TreeNode> queue = new LinkedList<TreeNode>();

queue.offer(root);

while (!queue.isEmpty()) {

TreeNode node = queue.poll();

TreeNode left = node.left;

node.left = node.right;

node.right = left;

if (node.left != null) {

queue.offer(node.left);

}

if (node.right != null) {

queue.offer(node.right);

}

}

return root;

}

\end{Code}

\section{Same Tree} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

\subsubsection{Solution}

\begin{Code}

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);

}

\end{Code}

\section{Binary Search Tree Iterator} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

\textbf{Note:}

next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

\subsubsection{Solution}

\begin{Code}

public class BSTIterator {

private Stack<TreeNode> mStack;

private TreeNode mCurNode;

public BSTIterator(TreeNode root) {

mStack = new Stack<TreeNode>();

mCurNode = root;

}

public boolean hasNext() {

return !mStack.isEmpty() || mCurNode != null;

}

public int next() {

int result = -1;

while (hasNext()) {

if (mCurNode != null) {

mStack.push(mCurNode);

mCurNode = mCurNode.left;

} else {

mCurNode = mStack.pop();

result = mCurNode.val;

mCurNode = mCurNode.right;

break;

}

}

return result;

}

}

\end{Code}

\section{Lowest Common Ancestor of a Binary Search Tree} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

\begin{Code}

_______6______

/ \

___2__ ___8__

/ \ / \

0 _4 7 9

/ \

3 5

\end{Code}

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

\subsubsection{Solution}

\begin{Code}

// 耗时9ms

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if (!checkExist(root, p) || !checkExist(root, q)) {

throw new IllegalArgumentException("Not exist!!");

}

while (root != null) {

if (p.val < root.val && q.val < root.val) {

root = root.left;

} else if (p.val > root.val && q.val > root.val) {

root = root.right;

} else {

break;

}

}

return root;

}

/**

* 如何判断p或q一定存在，如果是BST就很简单

*/

private boolean checkExist(TreeNode root, TreeNode node) {

TreeNode cur = root;

while (cur != null) {

if (node.val > cur.val) {

cur = cur.right;

} else if (node.val < cur.val) {

cur = cur.left;

} else {

return true;

}

}

return false;

}

\end{Code}

\section{Balanced Binary Tree} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

\subsubsection{Solution}

\begin{Code}

public boolean isBalanced(TreeNode root) {

return isBalanced(root, null);

}

private boolean isBalanced(TreeNode root, int[] height) {

if (root == null) {

return true;

}

int[] left = new int[1], right = new int[1];

boolean result = isBalanced(root.left, left) && isBalanced(root.right, right);

if (height != null) {

height[0] = Math.max(left[0], right[0]) + 1;

}

return result && Math.abs(left[0] - right[0]) <= 1;

}

\end{Code}

\section{Binary Tree Maximum Path Sum} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:

Given the below binary tree,

\begin{Code}

1

/ \

2 3

\end{Code}

Return 6.

\subsubsection{Solution}

\begin{Code}

public int maxPathSum(TreeNode root) {

return maxPathSum(root, null);

}

/**

* max表示包含root的单边路径最大和

*/

private int maxPathSum(TreeNode root, int[] max) {

if (root == null) {

return Integer.MIN_VALUE; // 此处容易错

}

int[] left = new int[1], right = new int[1];

int leftMax = maxPathSum(root.left, left);

int rightMax = maxPathSum(root.right, right);

if (max != null) {

// 三种情况：root, root+left, root+right

max[0] = max(left[0], right[0], 0) + root.val;

}

// 容易错，要考虑到所有可能的情况

// 左边里面的，右边里面的，光root的，左中右，左中，中右

return max(leftMax, rightMax, root.val, left[0] + right[0] + root.val,

left[0] + root.val, right[0] + root.val);

}

private int max(int... vals) {

int max = Integer.MIN_VALUE;

for (int val : vals) {

max = Math.max(max, val);

}

return max;

}

\end{Code}

\section{Populating Next Right Pointers in Each Node} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

Given a binary tree

\begin{Code}

struct TreeLinkNode {

TreeLinkNode *left;

TreeLinkNode *right;

TreeLinkNode *next;

}

\end{Code}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

\textbf{Note:}

You may only use constant extra space.

You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,

Given the following perfect binary tree,

\begin{Code}

1

/ \

2 3

/ \ / \

4 5 6 7

\end{Code}

After calling your function, the tree should look like:

\begin{Code}

1 -> NULL

/ \

2 -> 3 -> NULL

/ \ / \

4->5->6->7 -> NULL

\end{Code}

\subsubsection{Solution I}

\begin{Code}

/** 递归法，巧妙地运用dummy使代码很简洁

* 假定当前root所在层已连好，要连下一层

*/

public void connect(TreeLinkNode root) {

if (root == null) {

return;

}

TreeLinkNode dummy = new TreeLinkNode(0), cur = dummy;

for (TreeLinkNode p = root; p != null; p = p.next) {

if (p.left != null) {

cur.next = p.left;

cur = cur.next;

}

if (p.right != null) {

cur.next = p.right;

cur = cur.next;

}

}

connect(dummy.next);

}

\end{Code}

\subsubsection{Solution II}

\begin{Code}

/**

* 将递归转成非递归很简单，就加一层循环，且结尾处加root = dummy.next即可

*/

public void connect2(TreeLinkNode root) {

while (root != null) {

TreeLinkNode dummy = new TreeLinkNode(0), cur = dummy;

for (TreeLinkNode p = root; p != null; p = p.next) {

if (p.left != null) {

cur.next = p.left;

cur = cur.next;

}

if (p.right != null) {

cur.next = p.right;

cur = cur.next;

}

}

root = dummy.next;

}

}

\end{Code}

\section{Convert Sorted Array to Binary Search Tree} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

\subsubsection{Solution}

\begin{Code}

public TreeNode sortedArrayToBST(int[] nums) {

return sortedArrayToBST(nums, 0, nums.length);

}

private TreeNode sortedArrayToBST(int[] nums, int start, int end) {

if (start >= end) {

return null;

}

int mid = start + (end - start) / 2;

TreeNode root = new TreeNode(nums[mid]);

root.left = sortedArrayToBST(nums, start, mid);

root.right = sortedArrayToBST(nums, mid + 1, end);

return root;

}

\end{Code}

\section{Symmetric Tree} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree \code{[1,2,2,3,4,4,3]} is symmetric:

\begin{Code}

1

/ \

2 2

/ \ / \

3 4 4 3

\end{Code}

But the following \code{[1,2,2,null,3,null,3]} is not:

\begin{Code}

1

/ \

2 2

\ \

3 3

\end{Code}

\textbf{Note:}

Bonus points if you could solve it both recursively and iteratively.

\subsubsection{Solution}

\begin{Code}

public boolean isSymmetric(TreeNode root) {

if (root == null) {

return true;

}

return isSymmetric(root.left, root.right);

}

private boolean isSymmetric(TreeNode left, TreeNode right) {

if (left == null && right == null) {

return true;

}

if (left == null || right == null) {

return false;

}

return left.val == right.val && isSymmetric(left.left, right.right)

&& isSymmetric(left.right, right.left);

}

\end{Code}

\section{Lowest Common Ancestor of a Binary Tree} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

\begin{Code}

_______3______

/ \

___5__ ___1__

/ \ / \

6 _2 0 8

/ \

7 4

\end{Code}

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

\subsubsection{Solution I}

\begin{Code}

/**

* leetcode测试用例中p和q一定是在树中的

* 奇怪的是如果判断用root.val == p.val这种就不能AC，必须用root == p

* 确实，树中可能会存在值重复的节点

*/

// 耗时11ms

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if (root == null || root == p || root == q) {

return root;

}

TreeNode left = lowestCommonAncestor(root.left, p, q);

TreeNode right = lowestCommonAncestor(root.right, p, q);

if (left != null) {

return right != null ? root : left;

} else {

return right;

}

}

\end{Code}

\subsubsection{Solution II}

\begin{Code}

/**

* 这是迭代写法，另外考虑了p或者q不在树中的情况

* 用一个map保存每个node的前驱节点，当p和q同时找到了则回溯他们的前驱节点查看是否重合。

* 如果树遍历完了还没有同时找到p和q则返回null

*/

/**

* 耗时29ms

*/

public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {

if (root == null || p == null || q == null) {

return null;

}

HashMap<TreeNode, TreeNode> parents = new HashMap<>();

parents.put(root, null);

Queue<TreeNode> queue = new LinkedList<>();

queue.add(root);

while (!queue.isEmpty()) {

if (parents.containsKey(p) && parents.containsKey(q)) {

break;

}

TreeNode node = queue.poll();

if (node.left != null) {

queue.add(node.left);

parents.put(node.left, node);

}

if (node.right != null) {

queue.add(node.right);

parents.put(node.right, node);

}

}

if (!parents.containsKey(p) || !parents.containsKey(q)) {

return null;

}

Set<TreeNode> set = new HashSet<TreeNode>();

for (TreeNode node = p; node != null; node = parents.get(node)) {

set.add(node);

}

for (TreeNode node = q; node != null; node = parents.get(node)) {

if (set.contains(node)) {

return node;

}

}

return null;

}

\end{Code}

\section{Binary Tree Level Order Traversal} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:

\begin{Code}

Given binary tree [3,9,20,null,null,15,7],

3 [

/ \ [3],

9 20 return its level order traversal as: [9,20],

/ \ [15,7]

15 7 ]

\end{Code}

\subsubsection{Solution}

\begin{Code}

public List<List<Integer>> levelOrder(TreeNode root) {

List<List<Integer>> result = new LinkedList<List<Integer>>();

if (root == null) {

return result;

}

Queue<TreeNode> queue = new LinkedList<TreeNode>();

Queue<TreeNode> next = new LinkedList<TreeNode>();

queue.add(root);

List<Integer> cur = null;

while (!queue.isEmpty()) {

TreeNode node = queue.poll();

if (cur == null) {

cur = new LinkedList<Integer>();

result.add(cur);

}

cur.add(node.val);

if (node.left != null) {

next.add(node.left);

}

if (node.right != null) {

next.add(node.right);

}

if (queue.isEmpty()) {

Queue<TreeNode> temp = queue;

queue = next;

next = temp;

cur = null; // 注意这里要置空

}

}

return result;

}

\end{Code}

\section{Binary Tree Level Order Traversal II} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:

Given binary tree [3,9,20,null,null,15,7],

\begin{Code}

3

/ \

9 20

/ \

15 7

\end{Code}

return its bottom-up level order traversal as: [[15,7],[9,20],[3]]

\subsubsection{Solution}

\begin{Code}

public List<List<Integer>> levelOrder(TreeNode root) {

List<List<Integer>> result = new LinkedList<List<Integer>>();

if (root == null) { return result;}

Queue<TreeNode> queue = new LinkedList<TreeNode>();

Queue<TreeNode> next = new LinkedList<TreeNode>();

queue.add(root);

List<Integer> cur = null;

while (!queue.isEmpty()) {

TreeNode node = queue.poll();

if (cur == null) {

cur = new LinkedList<Integer>();

result.add(0, cur);

}

cur.add(node.val);

if (node.left != null) {

next.add(node.left);

}

if (node.right != null) {

next.add(node.right);

}

if (queue.isEmpty()) {

Queue<TreeNode> temp = queue;

queue = next;

next = temp;

cur = null; // 注意这里要置空

}

}

return result;

}

\end{Code}

\section{Binary Tree Zigzag Level Order Traversal} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:

Given binary tree \code{[3,9,20,null,null,15,7]},

\begin{Code}

3

/ \

9 20

/ \

15 7

\end{Code}

return its zigzag level order traversal as: \code{[[3],[20,9],[15,7]]}

\subsubsection{Solution}

\begin{Code}

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

List<List<Integer>> result = new LinkedList<List<Integer>>();

if (root == null) {return result;}

List<TreeNode> seq = new LinkedList<TreeNode>();

List<TreeNode> tmp = new LinkedList<TreeNode>();

seq.add(root);

List<Integer> cur = new LinkedList<Integer>();

for (int level = 1; !seq.isEmpty(); ) {

TreeNode node = seq.remove(0);

if (level % 2 != 0) {

cur.add(node.val);

} else {

cur.add(0, node.val);

}

if (node.left != null) {

tmp.add(node.left);

}

if (node.right != null) {

tmp.add(node.right);

}

if (seq.isEmpty()) {

result.add(cur);

cur = new LinkedList<Integer>();

List<TreeNode> tt = seq;

seq = tmp;

tmp = tt;

level++;

}

}

return result;

}

\end{Code}

\section{Serialize and Deserialize Binary Tree} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

\begin{Code}

1

/ \

2 3

/ \

4 5

\end{Code}

as \code{"[1,2,3,null,null,4,5]"}, just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

\subsubsection{Solution I}

\begin{Code}

// 这里的分隔符是有讲究的，如果换成'.'则在split的时候要转义，但是','不用

private static final String SEP = ",";

// 这个尽可能短，节省空间

private static final String NULL = "X";

/** 递归版的 */

public String serialize(TreeNode root) {

StringBuilder sb = new StringBuilder();

if (root != null) {

sb.append(root.val).append(SEP);

sb.append(serialize(root.left)).append(SEP);

sb.append(serialize(root.right));

} else {

sb.append(NULL);

}

return sb.toString();

}

public TreeNode deserialize(String data) {

String[] texts = data.split(SEP);

Queue<String> queue = new LinkedList<String>(Arrays.asList(texts));

return helper(queue);

}

private TreeNode helper(Queue<String> queue) {

if (queue.isEmpty()) {

return null;

}

String text = queue.poll();

if (text.equals(NULL)) {

return null;

}

int val = Integer.valueOf(text);

TreeNode root = new TreeNode(val);

root.left = helper(queue);

root.right = helper(queue);

return root;

}

\end{Code}

\subsubsection{Solution II}

\begin{Code}

/** 下面是非递归版的DFS */

public String serialize2(TreeNode root) {

StringBuilder sb = new StringBuilder();

if (root == null) {

sb.append(NULL);

return sb.toString();

}

Stack<TreeNode> stack = new Stack<TreeNode>();

while (!stack.isEmpty() || root != null) {

if (root != null) {

sb.append(root.val);

stack.push(root);

root = root.left;

} else {

sb.append(NULL);

root = stack.pop().right;

}

sb.append(SEP);

}

return sb.toString();

}

public TreeNode deserialize2(String data) {

String[] texts = data.split(SEP);

Queue<String> queue = new LinkedList<String>(Arrays.asList(texts));

Deque<TreeNode> stack = new LinkedList<>();

TreeNode root = getNode(queue), node = root;

while (!queue.isEmpty()) {

if (node != null) {

stack.push(node);

node.left = getNode(queue);

node = node.left;

} else {

node = stack.pop();

node.right = getNode(queue);

node = node.right;

}

}

return root;

}

private TreeNode getNode(Queue<String> queue) {

if (queue.isEmpty()) {

return null;

}

String text = queue.poll();

if (text.equals(NULL)) {

return null;

}

return new TreeNode(Integer.parseInt(text));

}

\end{Code}

\subsubsection{Solution III}

\begin{Code}

/**

* BFS版的

*/

public String serialize3(TreeNode root) {

Queue<TreeNode> queue = new LinkedList<TreeNode>();

StringBuilder sb = new StringBuilder();

if (root == null) {

sb.append(NULL);

return sb.toString();

}

queue.add(root);

while (!queue.isEmpty()) {

TreeNode node = queue.poll();

if (node == null) {

sb.append(NULL).append(SEP);

continue;

}

sb.append(node.val).append(SEP);

queue.add(node.left);

queue.add(node.right);

}

return sb.toString();

}

public TreeNode deserialize3(String data) {

String[] text = data.split(SEP);

Queue<String> queue = new LinkedList<String>(Arrays.asList(text));

Queue<TreeNode> queue2 = new LinkedList<TreeNode>();

TreeNode root = getNode(queue);

queue2.add(root);

while (!queue2.isEmpty()) {

TreeNode node = queue2.poll();

if (node == null) {

continue;

}

node.left = getNode(queue);

queue2.add(node.left);

node.right = getNode(queue);

queue2.add(node.right);

}

return root;

}

\end{Code}

\section{Count Complete Tree Nodes} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

\subsubsection{Solution}

\begin{Code}

/** 适合通用的二叉树，但是对于完全二叉树会超时

public int countNodes(TreeNode root) {

if (root == null) {

return 0;

}

int count = 0;

Queue<TreeNode> queue = new LinkedList<TreeNode>();

queue.add(root);

while (!queue.isEmpty()) {

TreeNode node = queue.poll();

count++;

if (node.left != null) {

queue.add(node.left);

}

if (node.right != null) {

queue.add(node.right);

}

}