二叉树相关的题目
层序遍历
思路：利用队列进行层序遍历，类似与BFS。
这里举一个锯齿形层序遍历的例子（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
public static int MAXN = 2001;
public static TreeNode[] queue = new TreeNode[MAXN];
public static int l, r;
public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root != null) {
l = r = 0;
queue[r++] = root;
boolean reverse = false;
while (l < r) {
int size = r - l;
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = reverse ? r - 1 : l, j = reverse ? -1 : 1, k = 0; k < size; i += j, k++) {
TreeNode cur = queue[i];
list.add(cur.val);
}
for (int i = 0; i < size; i++) {
TreeNode cur = queue[l++];
if (cur.left != null) {
queue[r++] = cur.left;
}
if (cur.right != null) {
queue[r++] = cur.right;
}
}
ans.add(list);
reverse = !reverse;
}
}
return ans;
}
|
二叉树最大宽度
思路：利用队列进行层序遍历，并同步记录当前层节点的索引，将索引保存在数组中，最后计算每一层开始与结束的索引的差值，并返回最大值。想象为完全二叉树，对于节点i，其左子节点为2i，右子节点为2i+1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| public int widthOfBinaryTree(TreeNode root) {
TreeNode[] queue = new TreeNode[3001];
Long[] idQueue = new Long[3001];
int l=0;
int r=0;
if(root == null){
return 0;
}
queue[r] = root;
idQueue[r++] = 1L;
int ans = 0;
while(l<r){
int size = r-l;
ans = Math.max(ans,(int)(idQueue[r-1]-idQueue[l]+1));
for(int i=0;i<size;i++){
TreeNode node = queue[l];
long id = idQueue[l++];
if(node.left!=null){
queue[r] = node.left;
idQueue[r++] = id*2;
}
if(node.right!=null){
queue[r] =node.right;
idQueue[r++] = id*2+1;
}
}
}
return ans;
}
|
最大深度跟最小深度
思路：利用递归进行求解，对于每个节点，求左右子树的最大深度，并返回较大的值。（最小深度同理，但要处理根节点为空的情况，因为为空子问题返回0高度，但题目说的最小深度必须到叶节点，所以会干扰最小深度的计算，所以必须子节点不为空才能进行递归）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public int maxDepth(TreeNode root) {
return root == null ? 0 : Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}
public int minDepth(TreeNode root) {
if(root ==null){
return 0;
}
if(root.right ==null && root.left ==null){
return 1;
}
int lMin = Integer.MAX_VALUE;
int rMin =Integer.MAX_VALUE;
if(root.left!=null){
lMin = minDepth(root.left);
}
if(root.right!=null){
rMin = minDepth(root.right);
}
return Math.min(lMin,rMin)+1;
}
|
根据中序遍历和前序遍历构建二叉树
思路：
确定根节点：
前序遍历的第一个元素一定是整个树的根节点。
划分左右子树：
根据根节点在中序遍历中的位置，可以将中序遍历序列划分为左子树和右子树的中序遍历序列。
左子树的中序遍历序列位于根节点的左边，右子树的中序遍历序列位于根节点的右边。
递归构建：
根据左子树和右子树的中序遍历序列长度，可以在前序遍历序列中划分出对应的左子树和右子树的前序遍历序列。
递归地对左右子树进行上述操作，直到遍历序列为空，返回 null。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length == 0){
return null;
}
int len = preorder.length;
HashMap<Integer,Integer> map =new HashMap<>();
for(int i= 0;i<len;i++){
map.put(inorder[i],i);
}
return build(preorder,0,len-1,inorder,0,len-1,map);
}
public TreeNode build(int[] pre ,int l1,int r1,int[] in,int l2,int r2,HashMap<Integer,Integer> map){
if(l1>r1 || l2 > r2){
return null;
}
if(l1 == r1){
return new TreeNode(pre[l1]);
}
TreeNode head = new TreeNode(pre[l1]);
int k =map.get(pre[l1]);
head.left = build(pre,l1+1,k-l2+l1,in,l2,k-1,map);
head.right = build(pre,k-l2+l1+1,r1,in,k+1,r2,map);
return head;
}
|
二叉树的最近公共祖先
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode l = lowestCommonAncestor(root.left, p, q);
TreeNode r = lowestCommonAncestor(root.right, p, q);
if (l != null && r != null) {
return root;
}
if (l == null && r == null) {
return null;
}
return l != null ? l : r;
}
|
验证二叉搜索树
思路：每个点必须大于左树的最大值，小于右树最小值。递归验证即可。但注意把最大值设为Long.MIN_VALUE，最小值设为Long.MAX_VALUE（为了不对结果造成干扰）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| long max = Long.MIN_VALUE;
long min = Long.MAX_VALUE;
public boolean isValidBST(TreeNode root) {
if(root == null){
max = Long.MIN_VALUE;
min = Integer.MAX_VALUE;
return true;
}
Boolean lok = isValidBST(root.left);
long lmax = max;
long lmin = min;
Boolean rok = isValidBST(root.right);
long rmax = max;
long rmin = min;
max = Math.max(Math.max(lmax,rmax),root.val);
min = Math.min(Math.min(lmin,rmin),root.val);
return lok && rok && root.val > lmax && root.val< rmin;
}
|
wechat