【数据结构】二叉树必刷题

文章目录

1.相同的树
2.另一颗树的子树
3.二叉树的最大深度
4. 平衡二叉树
5.对称二叉树
6.二叉树遍历
7.二叉树的层序遍历
8.二叉树最近公共祖先
9.二叉搜索树与双向链表
10. 根据一棵树的前序遍历与中序遍历构造二叉树
11. 根据一棵树的中序遍历与后序遍历构造二叉树
12. 二叉树创建字符串
13. 二叉树前序非递归遍历实现
14. 二叉树中序非递归遍历实现
15. 二叉树后序非递归遍历实现

前面我们学习了二叉树的性质，下面是一些oj面试题供大家练习

1.相同的树

题目描述：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

思路：利用递归一步一步的判断每一个结点

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
        return true;
    }
    if (p == null || q == null || p.val != q.val) {
        return false;
    }
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
1
2
3
4
5
6
7
8
9

2.另一颗树的子树

题目描述给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

思路：一棵树是另一颗树的子树，有三种情况：两颗树相同，一棵树是另一颗左数的子树；一棵树是另一颗右数的子树；切入点：如何分割root，如何判断子树和另一颗数相同

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    	//当递归到最后一个结点都没有相等，说明不可能相同
        if (root == null) {
            return false;
        }
        //利用短路求值表达式，当找到一颗子树相同时返回
        return isSametree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }
    public boolean isSametree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSametree(p.left, q.left) && isSametree(p.right, q.right);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.二叉树的最大深度

题目描述：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

思路1：利用递归每一次经过一个结点深度加一，然后更新max，最后返回最大深度

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
}
1
2
3
4
5
6

思路2：BFS广度优先搜索，利用队列每一次进入向其入当前层中的所有结点，下一次根据这些结点再入下一层的所有结点，利用变量depth记录当前的深度。

public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                TreeNode cur = queue.poll();
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            depth++;
        }
        return depth;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

4. 平衡二叉树

题目描述：给定一个二叉树，判断它是否是高度平衡的二叉树(一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 )。

思路：本题主要就是要我们计算一个结点的左右子树的高度是否小于1，利用-1表示当前节点高度不平衡，

public boolean isBalanced(TreeNode root) {
    return Depth(root) >= 0;
}
public int Depth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = Depth(root.left);
    int right = Depth(root.right);
    if (left >= 0 && right >= 0 && Math.abs(left - right) <= 1) {
        return Math.max(left, right) + 1;
    } else {
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5.对称二叉树

题目描述：给你一个二叉树的根节点 root ，检查它是否轴对称。

思路1：递归判断每一颗子树是否相同即可

public boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return false;
    }
    return cmp(root.left, root.right);
}
public boolean cmp(TreeNode node1, TreeNode node2) {
    if (node1 == null && node2 == null) {
        return true;
    }
    if (node1 == null || node2 == null || node1.val != node2.val) {
        return false;
    }
    //这里仔细一点，判断的是对称二叉树，递归判断的子树是node1.left和node2.right 
    return cmp(node1.left, node2.right) && cmp(node1.right, node2.left);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

思路2：迭代法，利用队列把我们需要的结点入队，然后比较，这里我们要注意结点的入队顺序，按照结构添加

public boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return false;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root.left);
    queue.offer(root.right);

    while (!queue.isEmpty()) {
        TreeNode node1 = queue.poll();
        TreeNode node2 = queue.poll();
        //到达叶子节点
        if (node1 == null && node2 == null) {
            continue;
        }
        //结点值不同或者子树结构不同
        if (node1 == null || node2 == null || node1.val != node2.val) {
            return false;
        }
        queue.offer(node1.left);
        queue.offer(node2.right);
        queue.offer(node1.right);
        queue.offer(node2.left);
    }
    return true;
}
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

6.二叉树遍历

题目描述：读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）

思路：先构建出根节点，然后递归构建左右子树即可。

import java.util.*;
class TreeNode {
    public char val;
    public TreeNode left;
    public TreeNode right; 
    public TreeNode(char val) {
        this.val = val;
    }
}

public class Main {
    public static int i = 0;
    public static TreeNode createTree(String str) {
        TreeNode root = null;
        if (str.charAt(i) != '#') {
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        } else {
            i++;
        }
        return root;
    }
    
 public static void inOrder(TreeNode root) {
     if (root == null) {
         return;
     }
     inOrder(root.left);
     System.out.print(root.val + " ");
     inOrder(root.right);
 }
 
 
 public static void main(String[] args) {
     Scanner in = new Scanner(System.in);
     while (in.hasNextLine()) {
         String str = in.nextLine();
         TreeNode root = createTree(str);
         inOrder(root);
     }
 }
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
40
41
42
43

7.二叉树的层序遍历

题目描述：给你二叉树的根节点 root ，返回其节点值的层序遍历。

思路：利用队列遍历

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> list = new LinkedList<>();
    if (root == null) {
        return list;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> list1 = new ArrayList<>();
        while (size-- > 0) {
            TreeNode cur = queue.poll();
            list1.add(cur.val);
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
        list.add(list1);
    }
    return list;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

8.二叉树最近公共祖先

题目描述：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。公共祖先的概念

思路：分为三种情况：

情况 1，如果 p 和 q 都在以 root 为根的树中，函数返回的即是 p 和 q 的最近公共祖先节点。
情况 2，那如果 p 和 q 都不在以 root 为根的树中返回 null
情况 3，那如果 p 和 q 只有一个存在于 root 为根的树中呢？函数就会返回那个节点。
分析结果：
情况 1，如果 p 和 q 都在以 root 为根的树中，那么root的 left 和 right 一定分别是 p 和 q
情况 2，如果 p 和 q 都不在以 root 为根的树中，直接返回 null。
情况 3，如果 p 和 q 只有一个存在于 root 为根的树中，函数返回该节点。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
        return null;
    }
    //找到p q结点
    if (root == p || root == q) {
        return root;
    }
	//这时候去左右子树去寻找p q结点
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // 情况 1
    if (left != null && right != null) {
        return root;
    }
    //情况 2
    if (left == null && right == null) {
        return null;
    }
    //情况 3
    return left == null ? right : left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

思路2：利用之前求链表的交点的思想，我们用栈来存储从根节点到p q结点所经历的结点，然后先让栈容量大的先走差值步，随后同时比较栈中元素，如果遇到相同的就找到了，没有就为返回null
难点：如何求解并存储路径上的结点值;利用递归求解，

private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
      if (root == null || node == null) {
          return false;
      }
      //把当前结点入栈
      stack.push(root);
      //如果当前结点为我们寻找的，返回true
      if (root == node) {
          return true;
      }
      //利用flag1标记下一个结点的left是否是我们寻找的
      boolean flag1 = getPath(root.left, node, stack);
      if (flag1 == true) {
          return true;
      }
      //利用flag2标记下一个结点的left是否是我们寻找的
      boolean flag2 = getPath(root.right, node, stack);
      if (flag2 == true) {
          return true;
      }
      //如果当前结点左右都不是，那么直接弹出该结点
      stack.pop();
      //返回false,说明结点不是路径上的
      return false;
  }
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      Stack<TreeNode> stack1 = new Stack<>();
      Stack<TreeNode> stack2 = new Stack<>();
      getPath(root, p, stack1);
      getPath(root, q, stack2);
      //先走差值步
      int size1 = stack1.size();
      int size2 = stack2.size();
      int k = Math.abs(size1 - size2);
      if (size1 > size2) {
          while (k-- > 0) {
              stack1.pop();
          }     
      } else if (size1 < size2) {
          while (k-- > 0) {
              stack2.pop();
          }  
      } 
      //寻找相同结点
      while (!stack1.isEmpty() && !stack2.isEmpty()) {
          if (stack1.peek() == stack2.peek()) {
              return stack2.peek();
          } else {
              stack1.pop();
              stack2.pop();
          }
      }
      return 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

9.二叉搜索树与双向链表

题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表

思路一：利用二叉搜索树的性质，它的中序遍历的结果为排序好的值，所以我们可以在中序遍历时修改结点的指向，把它变成双向链表；定义一个前驱指针prev为null，先递归找到头结点，这里很清楚的知道结点的left相当于链表中的prev,right相当于链表的next;然后
改变指向。

TreeNode prev = null;
private void ConvertChild(TreeNode pCur) {
    if (pCur== null) {
        return;
    }  
    ConvertChild(pCur.left);
    pCur.left = prev;
    if (prev != null) {
        prev.right = pCur;
    }
    prev = pCur;
    ConvertChild(pCur.right);
    
}
public TreeNode Convert(TreeNode root) {
    if (root == null) {
        return null;
    }
    ConvertChild(root);
    TreeNode head = root;
    while(head.left != null) {
        head = head.left;
    }
    return head;
}
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

思路二;这里是利用位结点来链接

//指向当前链表的末尾节点
private TreeNode pLast = null;
public TreeNode Convert(TreeNode root) {
    if (root == null) {
        return null;
    }
    //找到链表头,这里已经在递归左子树了
    TreeNode head = Convert(root.left);
    //处理特殊情况：如果左子树为空，则根为链表头
    if (head == null) {
        head = root;
    }
    //开始处理，left相当于pre;rigth相当于next
    root.left = pLast;
    if (pLast != null) {
        pLast.right = root;
    }
    //更新末尾指向
    pLast = root;
    
    Convert(root.right);
    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

10. 根据一棵树的前序遍历与中序遍历构造二叉树

题目描述：给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

思路：在做这道题使我们先要知道如何通过前序遍历和中序遍历来构建二叉树，例如
前序遍历：EFHIGJK;中序遍历：HFIEJKG.前序遍历的第一个肯定是根结点，然后在中序遍历中找到它，这时候它的左边为它的左子树，右边为它的右子树。如何继续前序遍历找到另一颗子树的根节点，递归构建

先把中序遍历的对应的值-下标存放到hashMap中，在后面可以直接通过val找到下标
通过先序遍历找到每一个子树根节点的位置标记为index,得到左子树的长度leftSize = index - in_start;然后递归构建左右子树

//存放 值 <=>下标 键对
HashMap<Integer, Integer> map = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {     
    for (int i = 0; i < inorder.length; i++) {
        map.put(inorder[i], i);
    }
    return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
TreeNode build(int[] preorder, int pre_start, int pre_end, int[] inorder, int in_start, int in_end) {
	//说明此时没有左右子树
    if (pre_start > pre_end) return null;
    //根节点的val
    int rootVal = preorder[pre_start];
    //当前val 在中序遍历中的索引
    int index = map.get(rootVal);
    int leftSize = index - in_start;
    TreeNode root = new TreeNode(rootVal);
    //画图理解范围变化
    //递归构建
    root.left = build(preorder, pre_start + 1, pre_start + leftSize, inorder, in_start, index - 1);
    root.right = build(preorder, pre_start + leftSize + 1,pre_end, inorder, index + 1, in_end);
    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

另一种不使用hashMap的方法：

public int preIndex = 0;
public TreeNode build(int[] preorder, int[] inorder, int inBegin, int inEnd) {
    if (inBegin > inEnd) {
        return null;
    }
    TreeNode root = new TreeNode(preorder[preIndex]);
    //找到根节点在中序遍历的位置
    int rootIndex = findInorderRootIndex(inorder, inBegin, inEnd, preorder[preIndex]);
    preIndex++;

    root.left = build(preorder, inorder, inBegin, rootIndex - 1);
    root.right = build(preorder, inorder, rootIndex + 1, inEnd);

    return root;
}

private int findInorderRootIndex(int[] inorder, int inBegin, int inEnd, int val) {
    for (int i = inBegin; i <= inEnd; i++) {
        if (inorder[i] == val) {
            return i;
        }
    }
    return -1;
}

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, 0, inorder.length - 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

11. 根据一棵树的中序遍历与后序遍历构造二叉树

题目描述：给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。

思路同上：
在这里插入图片描述

HashMap<Integer, Integer> map = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
    for (int i = 0; i < postorder.length; i++) {
        map.put(inorder[i], i);
    }
    return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
/**
    中序遍历数组为 inorder[inStart..inEnd]，
   后序遍历数组为 postorder[postStart..postEnd]，
 */
TreeNode build(int[] inorder, int in_start, int in_end, int[] postorder, int post_start, int post_end) {
    if (in_start > in_end) return null;
    // root 节点对应的值就是后序遍历数组的最后一个元素
    int rootVal = postorder[post_end];
    // rootVal 在中序遍历数组中的索引
    int index = map.get(rootVal);
    // 左子树的节点个数
    int leftSize = index - in_start;

    TreeNode root = new TreeNode(rootVal);

    root.left = build(inorder, in_start, index - 1, postorder, post_start, post_start + leftSize -1);
    root.right = build(inorder, index + 1, in_end, postorder, post_start + leftSize, post_end - 1);
    return root;
}
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

解法2：

public int postIndex = 0;
public TreeNode buildTreeChild(int[] postorder, int[] inorder,int inbegin,int inend) {
    if(inbegin > inend) return null;//说明此时，没有左树或者右树

    TreeNode root = new TreeNode(postorder[postIndex]);

    //1、找到根节点在中序遍历当中的位置
    int rootIndex = findInorderRootIndex(inorder,inbegin,inend,postorder[postIndex]);
    postIndex--;

    root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);
    root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);

    return root;

}

private int findInorderRootIndex(int[] inorder,int inbegin,int inend,int val) {
    for(int i = inbegin;i <= inend;i++) {
        if(inorder[i] == val) {
            return i;
        }
    }
    return -1;//没有val这个数据
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
    postIndex = postorder.length-1;
    return buildTreeChild(postorder,inorder,0,inorder.length-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

12. 二叉树创建字符串

题目描述:给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串

public String tree2str(TreeNode root) { 
    StringBuffer sb = new StringBuffer();
    creatStr(root, sb);
    return sb.toString();
}
private void creatStr(TreeNode node, StringBuffer sb) {
    if (node != null) {
        sb.append(node.val);
        //节点的左右节点有一个不为空,至少有一个括号
        if (node.left != null || node.right != null) {
            sb.append('(');
            //由于是先序遍历，所以先遍历左子树
            creatStr(node.left, sb);
            sb.append(')');
            //如果右子树为空，括号可以省略，
            if (node.right != null) {
                sb.append('(');
                creatStr(node.right, sb);
                sb.append(')');
            }
        }
        //这里说明左右节点都为空，不需要做什么
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

13. 二叉树前序非递归遍历实现

题目描述：给你二叉树的根节点 root ，返回它节点值的前序遍历。

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        //二者顺序不能交换，一定要保证栈有数据
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                list.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            cur = cur.right;
        }
        return list;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

14. 二叉树中序非递归遍历实现

题目描述：给定一个二叉树的根节点 root ，返回它的中序遍历。

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            //由于是左-根-右 所以要先遍历到 左子树结点，然后父节点，最后才是右节点
            list.add(cur.val);
            cur = cur.right;
        }
        return list;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

15. 二叉树后序非递归遍历实现

题目描述：给你一棵二叉树的根节点 root ，返回其节点值的后序遍历

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode pre = null; //记录上一个节点
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.peek();
            //检查该结点的右是否遍历过了,否则会出现死循环
            if (cur.right == null || cur.right == pre) {
                list.add(cur.val);
                stack.pop();
                pre = cur;
                cur = null;
            } else {
                cur = cur.right;
            }
        }
        return list;
    }
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

相关阅读:
Java异常03：自定义异常及经验小结
 使用@check方法获取id集合
 云服务器CentOS8.2安装部署Docker一文详解
 《代码整洁之道》精华速览，助你提升代码质量
 Java8中Optional解决空指针异常
 oracle提高执行更新或新增的SQL效率
 队列（C语言实现）
【T+】畅捷通T+增加会计科目提示执行超时已过期。
南大通用GBase8s 常用SQL语句（255）
在AndroidR user版本的设备上，如何默认打开USB调试，如何去掉USB调试确认弹窗
原文地址：https://blog.csdn.net/weixin_61543874/article/details/125503073