面试题7：重建二叉树
题目：
输入某二叉树的前序遍历和中序遍历的结果。请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如，输入的前序遍历序列{1，2，4，7，3，5，6，8}和中序遍历序列{4，7，2，1，5，3，8，6}，则重建如图所示的二叉树并输出它的头节点。
1
/ \
2 3
/ / \
4 5 6
\ /
7 8
思路：
前序遍历的第一个数字就是根节点的值，扫描中序遍历序列，就能确定根节点的值。根据终须遍历的特点，在根节点的值前面的数字都是左子树的值，位于根节点后面的值都是右子树的节点的值。
代码实现：
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
/******
* 前序遍历的第一个数便是根节点，在中序遍历的数组中找到根节点位置，便可以分别找到左子树
* 和右子树的数目和位置，再分别递归左右子树，得到根节点的左右子节点
**/
public class Solution {
/**
*@param preorder : A list of integers that preorder traversal of a tree
*@param inorder : A list of integers that inorder traversal of a tree
*@return : Root of a tree
*/
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length != inorder.length ) {
return null;
}
return myBuildTree(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
}
private TreeNode myBuildTree(int[] preorder, int prestart, int preend,
int[] inorder, int instart, int inend) {
//
if (instart > inend || prestart > preend) {
return null;
}
TreeNode root = new TreeNode(preorder[prestart]);
int pos = findPos(inorder, instart, inend, preorder[prestart]);
root.left = myBuildTree(preorder, prestart+1,prestart+pos-instart,
inorder,instart, pos-1);
root.right = myBuildTree(preorder, prestart+pos-instart+1,preend,
inorder, pos+1, inend);
return root;
}
private int findPos(int[] nums,int start, int end, int target) {
int pos = 0;
for(int i = start; i <= end; i++) {
if (nums[i] == target) {
pos = i;
}
}
return pos;
}
}
面试题8：二叉树的下一个节点
题目：
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路：
此题包含三步：
- 如果此节点有右子树，下一个节点为右子节点的最左边的节点。
- 如果此节点没有右子树，并且如果此节点是其父节点的左子节点，则下一个节点为父节点。
- 如果此节点没有右子树，并且如果此节点是其父节点的右子节点，则一直向上找，直到找到第一个是其父节点左节点的节点，下一个节点就为此节点。
代码实现 ：
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param T1, T2: The roots of binary tree.
* @return: True if T2 is a subtree of T1, or false.
*/
public boolean isSubtree(TreeNode T1, TreeNode T2) {
//先判断T2，再判断T1
if (T2 == null) {
return true;
}
if (T1 == null) {
return false;
}
//从根节点出发判断，就相当于判断二者是否相等
if (isEqual(T1, T2)) {
return true;
}
if (isSubtree(T1.left, T2) || isSubtree(T1.right, T2)) {
return true;
}
return false;
}
private boolean isEqual(TreeNode n1, TreeNode n2) {
if (n1 == null || n2 == null) {
return n1 == n2;
}
if (n1.val != n2.val) {
return false;
}
return isEqual(n1.left, n2.left) && isEqual(n1.right, n2.right);
}
}
面试26：树的子结构
题目：
输入两颗二叉树A和B，判断B是不是A的子结构
样例：
下面的例子中 T2 是 T1 的子树：
1 3
/ \ /
T1 = 2 3 T2 = 4
/
4
下面的例子中 T2 不是 T1 的子树：
1 3
/ \ \
T1 = 2 3 T2 = 4
/
4
代码实现：
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param T1, T2: The roots of binary tree.
* @return: True if T2 is a subtree of T1, or false.
*/
public boolean isSubtree(TreeNode T1, TreeNode T2) {
//必须先判断T2，再判断T1
if (T2 == null) {
return true;
}
if (T1 == null) {
return false;
}
if (isEqual(T1, T2)) {
return true;
}
if (isSubtree(T1.left, T2) || isSubtree(T1.right, T2)) {
return true;
}
return false;
}
private boolean isEqual(TreeNode T1, TreeNode T2) {
if (T1 == null || T2 == null) {
return T1 == T2;
}
if (T1.val != T2.val) {
return false;
}
return isEqual(T1.left, T2.left) && isEqual(T1.right, T2.right);
}
}
面试27:二叉树的镜像
题目：
请完成一个函数，输入一颗二叉树，该函数输出它的镜像
样例：
1 1
/ \ / \
2 3 => 3 2
/ \
4 4
代码实现：
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
public void invertBinaryTree(TreeNode root) {
if (root == null) {
return;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertBinaryTree(root.left);
invertBinaryTree(root.right);
}
}
面试题28： 对称的二叉树
题目：
请实现一个函数，用来判断一颗二叉树是不是对称的。如果一颗二叉树和它的镜像一样，那么它是对称的。
样例：
8 8 8
/ \ / \ / \
6 6 6 9 7 7
/ \ / \ / \ / \ / \ /
5 7 7 5 5 7 7 5 7 7 7
3棵二叉树，其中第一棵是对称的，另外两棵不是
代码实现：
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
public boolean isSymmetrical(TreeNode root) {
if (root == null) {
return true;
}
return check(root.left, root.right);
}
private boolean check(TreeNode T1, TreeNode T2) {
if (T1 == null || T2 == null) {
return T1 == T2;
}
if (T1.val != T2.val) {
return false;
}
return check(T1.left, T2.right) && check(T1.right, T2.left);
}
}
面试题33：二叉搜索树的后序遍历序列
题目：
输入一个整数数组，判断该数组是不是某二叉搜索书的后序遍历结果。如果是则返回true，否则返回false。假设输入的数组的任意连个数字都不相同。
样例：
8
/ \
6 10
/ \ / \
5 7 9 11
后序遍历序列{5，7，6，9，11，10，8}对应的二叉搜索树
思路：
在后序遍历得到的序列中，最后一个数字是树的根结点的值。数组中前面的数字可以分为两部分：第一部分是左子树根结点的值，它们都比根结点的值小；第二部分是右子树根结点的值，它们都比根结点的值大。
如果要求处理一棵二叉树的遍历序列，我们可以先找到二叉树的根结点，再基于根结点把整棵树的遍历序列拆分成左子树对应的子序列和右子树对应的子序列，接下来再递归地处理这两个子序列。
代码实现：
public class VerifySequenceBST {
public static boolean verifySequenceBST(int[] seq) {
if (seq == null || seq.length == 0) {
return false;
}
return verifySequenceBST(seq, 0, seq.length-1);
}
private static boolean verifySequenceBST(int[] seq, int start, int end) {
if (start > end) {
return true;
}
int root = seq[end];
//在二叉搜索树中左子树节点的值小于根节点的值
int i = start;
while (i < end) {
if (seq[i] > root) {
break;
}
i++;
}
//在二叉搜索树中右子树节点的值大于根节点的值
int j = i;
while (j < end) {
if (seq[j] < root) {
return false;
}
j++;
}
boolean left = true;
//判断左子树是不是二叉搜索树
left = verifySequenceBST(seq, start, i-1);
boolean right = true;
//判断右子树是不是二叉搜索树
right = verifySequenceBST(seq, i, end - 1);
return left & right;
}
public static void main(String[] args) {
int[] seq1 = {5,7,6,9,11,10,8};
int[] seq2 = {7,4,6,5};
System.out.println(verifySequenceBST(seq1));
System.out.println(verifySequenceBST(seq2));
}
}
面试题34： 二叉树中和为某一值的路径
题目：
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从根节点开始往下一直到叶节点所经过的节点形成一条路径
样例
给定一个二叉树，和 目标值 = 5:
1
/ \
2 4
/ \
2 3
返回：
[
[1, 2, 2],
[1, 4]
]
代码实现
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root the root of binary tree
* @param target an integer
* @return all valid paths
*/
// List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
List<Integer> path = new ArrayList<>();
path.add(root.val);
dfs(root, root.val, target, path, result);
return result;
}
private void dfs(TreeNode root, int sum, int target, List<Integer> path,
List<List<Integer>> result) {
// meat leaf
if (root.left == null && root.right == null) {
if (sum == target) {
result.add(new ArrayList<>(path));
}
return;
}
// go left
if (root.left != null) {
path.add(root.left.val);
// notdfs(root, sum+root.left.val, target, path, result);
dfs(root.left, sum+root.left.val, target, path, result);
//去掉上一次加入的节点 dfs
path.remove(path.size()-1);
}
//go right
if (root.right != null) {
path.add(root.right.val);
//dfs(root, sum+root.right.val, target, path, result);
dfs(root.right, sum+root.right.val, target, path, result);
path.remove(path.size()-1);
}
}
}
面试题36：二叉搜索树与双向链表
题目：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
思路：
按照中序遍历的顺序，当遍历转换到根节点时，它的左子树已经转换成一个排序链表了，并且处在链表中的最后一个节点是当前值最大的节点。把左子树中最大的节点和根节点连接起来，此时链表中的最后一个节点就是根节点。接着遍历右子树，并把根结点和右子树中最小的节点连接起来。至于怎么转换它的左子树和右子树，由于遍历和转换过程是一样的，可以用递归。
代码实现：
public static BinaryTreeNode convert(BinaryTreeNode root){
BinaryTreeNode lastNodeInList = null;
lastNodeInList = convertNode(root,lastNodeInList);
//lastNOdeList指向双向链表的尾节点
//我们需要返回头节点
BinaryTreeNode headOfList = lastNodeInList;
while(headOfList!=null && headOfList.left!=null){
headOfList = headOfList.left;
}
return headOfList;
}
public static BinaryTreeNode convertNode(BinaryTreeNode node, BinaryTreeNode lastNodeInList){
if(node==null)
return null;
BinaryTreeNode current = node;
if(current.left!=null)
lastNodeInList = convertNode(current.left,lastNodeInList);
current.left = lastNodeInList;
if(lastNodeInList!=null)
lastNodeInList.right = current;
lastNodeInList = current;
if(current.right!=null)
lastNodeInList = convertNode(current.right,lastNodeInList);
return lastNodeInList;
}
}
面试题37 ： 二叉树的序列化和反序列化
题目：
设计一个算法，并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为 “序列化”，读取文件后重建同样的二叉树被称为 “反序列化”。
如何反序列化或序列化二叉树是没有限制的，你只需要确保可以将二叉树序列化为一个字符串，并且可以将字符串反序列化为原来的树结构。
代码实现：
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
class Solution {
/**
* This method will be invoked first, you should design your own algorithm
* to serialize a binary tree which denote by a root node to a string which
* can be easily deserialized by your own "deserialize" method later.
*/
public String serialize(TreeNode root) {
if(root == null) {
return "{}";
}
ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
queue.add(root);
//add all node to queue
for(int i = 0; i < queue.size(); i++) {
//TreeNode node = queue.get(i);
if (queue.get(i) == null) {
continue;
}
queue.add(queue.get(i).left);
queue.add(queue.get(i).right);
}
//remove last null node
//serialize
StringBuilder sb = new StringBuilder();
sb.append("{");
sb.append(queue.get(0).val);
for(int j = 1; j < queue.size(); j++) {
if (queue.get(j) == null) {
sb.append(",#");
} else {
sb.append("," + queue.get(j).val);
}
}
sb.append("}");
return sb.toString();
}
/**
* This method will be invoked second, the argument data is what exactly
* you serialized at method "serialize", that means the data is not given by
* system, it's given by your own serialize method. So the format of data is
* designed by yourself, and deserialize it here as you serialize it in
* "serialize" method.
*/
public TreeNode deserialize(String data) {
// write your code here
if (data.equals("{}")) {
return null;
}
String[] vals = data.substring(1, data.length() - 1).split(",");
ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
queue.add(root);
int index = 0;
boolean isLeftChild = true;
for (int i = 1; i < vals.length; i++) {
if (!vals[i].equals("#")) {
TreeNode node = new TreeNode(Integer.parseInt(vals[i]));
if (isLeftChild) {
queue.get(index).left = node;
} else {
queue.get(index).right = node;
}
queue.add(node);
}
if (!isLeftChild) {
index++;
}
isLeftChild = !isLeftChild;
}
return root;
}
}
面试题54: 二叉搜索树的第K大节点
题目：
给定一棵二叉搜索树，请找出其中第K大的节点。
样例：
5
/ \
3 7
/ \ / \
2 4 6 8
按节点数值的大小顺序，第三大节点的值是4
思路 ：
如果按照中序遍历的顺序遍历一棵二叉搜索树，则遍历序列的数值是递增序列的。例如，中序遍历序列是{2，3，4，5，6，7，8}。因此，只需要用中序遍历算法遍历一棵二叉搜索树，我们就很容易找出它的第K大节点。
代码实现：
public class KthLargestNumInBST {
List<TreeNode> arr = new ArrayList<>();
public TreeNode kthNum(TreeNode root, int k) {
if (root == null || k == 0) {
return null;
}
inOrder(root);
if (k <= arr.size()) {
return arr.get(k);
}
return null;
}
private void inOrder(TreeNode root) {
if (root == null) {
return;
}
if (root.left != null) {
inOrder(root.left);
}
arr.add(root);
if (root.right != null) {
inOrder(root.right);
}
}
