网络知识 娱乐 笔试面试高频考点 12道经典题目带你走进 二叉树(2)——数据结构

笔试面试高频考点 12道经典题目带你走进 二叉树(2)——数据结构

题目:

  1. 判断一棵树是不是完全二叉树

  2. 求出二叉树的最大宽度

  3. 检查两颗树是否相同

  4. 判断一颗二叉树是否是平衡二叉树

  5. 判断是否是对称二叉树

  6. 二叉树改为镜像二叉树

  7. 二叉树的构建和遍历

  8. 找到该二叉树中两个指定节点的最近公共祖先

  9. 二叉搜索树转化为排序的双向链表

  10. 根据先序中序遍历序列构造二叉树历

  11. 根据中序后序遍历序列构造二叉树

  12. 二叉树创建字符串

前言:

​ 上一篇文章我们介绍了有关树和二叉树的基本概念知识 及 简单的二叉树基本操作,本篇文章紧接上集 通过 12 道二叉树经典题目的讲解,希望能让你对于面试、笔试中二叉树相关题目不再毫无头绪,收获自己独特的见解和思路,更好理解二叉树本身。

1 判断一棵树是不是完全二叉树

1)思路:

  • 使用队列保存根节点,初始化传入root

  • 单个节点的循环出队,判断出队的是否为空节点不是则入队该节点的子节点(无论子节点是否为空),否则跳出循环

  • 循环判断队列是否为空,遍历队列中的节点,节点为null出队,不为null则返回false

    • 虽然队列里面元素可能都为null,但是queue.isEmpty() 结果仍旧为 false,所以我们要一个一个把为null的元素出队

2)解法:

public boolean isCompleteTree(TreeNode root){
        if(root == null) return true;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            TreeNode tmp = queue.poll();
            //非空节点,直接将子节点都入队
            if(tmp != null){
                queue.offer(tmp.left);
                queue.offer(tmp.right);
                
            //遇到null节点直接提出循环
            }else{
                break;
            }
        }

        while(!queue.isEmpty()){
            TreeNode cur = queue.peek();
            if(cur == null){
                queue.poll();
            }else{
                return false;
            }
        }
        return true;
}

2 求出二叉树的最大宽度

662. 二叉树最大宽度

1)思路:

  • 总:和返回值为List的思路类似,针对每层节点进行操作,不过要对每个节点进行封装加入pos属性(节点在一层中的序号),利用pos找到每层的最大值
  • 节点进行封装加入pos创建新类TmpNode,创建queue 传入TempNode(root, 0)
  • 一次外循环中,对一层元素进行操作,在外循环内部创建 array保存每层元素的pos
  • 整个内循环中,进行出队遍历一层中的每个元素
    • 出队时对非空元素node进行入队,node左右子元素的pos分别为 pos(node本身pos)*2、pos * 2 + 1
    • 整个内循环结束,使用array保存的pos计算一层的宽度,和本层以上的最大宽度进行比较求最大值

2)解法:

public int widthOfBinaryTree1(TreeNode root) {
        if(root == null) return 0;
        Queue<TmpNode> queue = new LinkedList<>();
        queue.offer(new TmpNode(root, 0));
        int width = 0;
        
        while(!queue.isEmpty()){

            //保存一层中的元素序号
            ArrayList<Integer> array = new ArrayList<>();
            //直接分层进行操作,不需要引入额外的depth
            for(int i = queue.size(); i > 0; i--){
                TmpNode tmpNode = queue.poll();
                TreeNode node = tmpNode.node;
                int pos = tmpNode.pos;
                array.add(pos);
                
                if(node.left != null){
                    queue.offer(new TmpNode(node.left, pos * 2));
                }

                if(node.right != null){
                    queue.offer(new TmpNode(node.right, pos*2 + 1));
                }
            }
            
            //找到 本层宽度和本层以上宽度最大宽度 的较大值
            width = Math.max(width, array.get(array.size() - 1) - array.get(0) + 1);
        }

        return width;   
}

    //创建包含序号的新类
public class TmpNode{
        public TreeNode node;
        //表示仅在这一层的序号(每层从0开始)
        public int pos;
        
        public TmpNode(TreeNode node, int pos){
            this.node = node;
            this.pos = pos;
        }
}

3 检查两颗树是否相同

3.1 检查两颗树是否相同

100. 相同的树

1)思路:

  • 子问题思路,先检查根节点,再检查左右子树
  • 检查根节点(截至条件),为空情况,节点不一致情况检查左右节点(继续递归)
  • 递归检查左右子树

2)解法:

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

3)时间复杂度

  • O(n)

3.2 另一颗树的子树

572. 另一棵树的子树

1)思路:

  • 子问题思路,本质上还是检查两棵树是否相同,先检查根节点下对应树是否相同,不同,再检查左右子树是否相同
  • 使用另一个方法传入根节点和子树根节点比较两棵树是否相同,有一个根节点对应的树和子树相同则返回真

2)解法:

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    //判断subRoot是否是root的子树
    
    if(root == null) return false;

    //比较子树和根节点对应的树
    if(isSameTree(root, subRoot)) return true;

    //比较子树和左节点对应的树
    if(isSubtree(root.left, subRoot)) return true;

    //比较子树和右节点对应的树
    if(isSubtree(root.right, subRoot)) return true;

    return false;
}

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

3)时间复杂度

  • O(t * s)

    • t是subRoot的节点个数,s是root的节点个数

4 判断一颗二叉树是否是平衡二叉树

110. 平衡二叉树

平衡二叉树: 一个二叉树 每个节点左右两个子树的高度差 的绝对值不超过 1

1)思路:

  • 自上而上
    • 遍历到每个节点时都求 该节点左右子树的高度差,判断该树是否为完全二叉树
    • 时间复杂度 O(N^2)
  • 自下而上
    • 直接在一次求树高度的时候,判断左右树高度差值是否大于2,否则返回树高度为 -1
      • 子树高度可能为-1且不知道左右树那一个高,所以计算时需要使用Math.abs()求左右树高度绝对值
    • 因为在深层次的递归算出的子树高度可能为 - 1,所以在判断情况时还要加上 左右树高度>0
    • 时间复杂度,O(N)

2)解法:

  • 自上而下
public int maxDepth(TreeNode root) {
    if(root == null) return 0;

    int legftH = maxDepth(root.left);
    int rightH = maxDepth(root.right);

    return legftH > rightH ? legftH + 1 : rightH + 1;
}

public boolean isBalanced(TreeNode root) {
    if(root == null) return true;

    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    
    //除判断左右子树高度差外,还要判断左右子树是否为平衡二叉树
    return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    
}
  • 自下而上
public boolean isBalanced(TreeNode root) {
        return maxDepth(root) >= 0;
}

public int maxDepth(TreeNode root) {
    if(root == null) return 0;

    int leftH = maxDepth(root.left);
    int rightH = maxDepth(root.right);
    
    //判读左右树高度>0,且高度差不超过1 
    if(leftH >= 0 && rightH >= 0 && Math.abs(leftH - rightH) <= 1){
        return leftH > rightH ? leftH + 1 : rightH + 1;
    }else{
        return -1;
    }

}

5 判断是否是对称二叉树

101. 对称二叉树

1)思路:

  • 子问题思路,先比较左右根节点是否相同
  • 进入左根节点的左树 和 右根节点的右树,进行比较
  • 进入左根节点的右树 和 右根节点的左树,进行比较

2)解法:

public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
    if(leftTree == null && rightTree == null) return true;

    //左根节点、右根节点有一个为空,或者左右树根节点值不同
    if((leftTree != null && rightTree == null)
            || (rightTree != null && leftTree == null)
            || leftTree.val != rightTree.val) return false;

    //比较 左根节点的左树 和 右根节点的右树是否相同 + 左根节点的右树 和 右根节点的左树是否相同
    return isSymmetricChild(leftTree.left, rightTree.right) && isSymmetricChild(leftTree.right, rightTree.left);

}

public boolean isSymmetric(TreeNode root) {
    if(root == null) return true;
    return isSymmetricChild(root.left,root.right);
}

6 二叉树改为镜像二叉树

二叉树的镜像

操作给定的二叉树,将其变换为源二叉树的镜像

1)思路:

  • 子问题思路,交换左右子树
  • 中止条件是根节点为空 / 根节点左右子节点都为空
  • 交换根节点的左右子树(交换整个节点,不只是val值)
  • 对根节点 不为空的子树再进行镜像递归

2)解法:

public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot == null){
            return pRoot;
        }

        if(pRoot.left == null && pRoot.right == null){
            return pRoot;
        }

        //交换左右子树
        TreeNode tmp = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = tmp;

        //不为空的子树再进行镜像
        
        if(pRoot.left != null){
            Mirror(pRoot.left);
        }

        if(pRoot.right != null){
            Mirror(pRoot.right);
        }

        return pRoot;

}

7 二叉树的构建和遍历

二叉树遍历

用户输入的一串带有“#”的先序遍历字符串,根据此字符串建立一个二叉树,再对二叉树进行中序遍历,输出遍历结果

ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树

1)思路:

(1)中止条件为字符串为’#’

(2)递归遍历字符串,分情况字符不为 ‘#‘创建根递归创建根的左树和右树,字符串为’#’ i++

  • 因为要进行递归,i放在递归里面会被初识化,要设置**为全局变量**

2)解法:

import java.util.*;

public class Main{
    
    //静态内部类创建节点
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        
        public TreeNode(char val){
            this.val = val;
        }  
    }
    
    public static void inorder(TreeNode root){
        if(root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    } 
    
    //根据输入创建二叉树
    public static int i = 0;
    
    public static TreeNode creatBinaryTree(String str){
        TreeNode root = null;
        
        if(str.charAt(i) == '#'){
            i++;
            return root;
        }
        
        //创建根节点及左右子树
        root = new TreeNode(str.charAt(i));
        i++;
        
        root.left = creatBinaryTree(str);
        root.right = creatBinaryTree(str);
        
        return root;
        
    }
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
       
        while(scanner.hasNextLine()){
            String str = scanner.nextLine();
            Main.TreeNode root = creatBinaryTree(str);
            inorder(root);
            System.out.println();
        }
    }
}

8 二叉树, 找到该树中两个指定节点的最近公共祖先

236. 二叉树的最近公共祖先

1)思路:

(1)递归:

  • 递归中止条件是**root == null**

  • 子问题的思路在左树右树寻找,找到分情况判断

    • 左右树都不为空 返回root
    • 左右树一个不为空,返回不为空的
    • 到最后说明都为空,直接返回null

2)解法:

  • 递归:
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
         //递归
         if(root == null) return null;

         if(p == root || q == root) return root;

         //在左右树中寻找
         TreeNode leftRet = lowestCommonAncestor(root.left, p, q);

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

         //左右都有返回根节点,否则返回相应左右树中的根节点
         if(leftRet != null && rightRet != null){
             return root;
         }else if(leftRet != null){
             return leftRet;
         }else if(rightRet != null){
             return rightRet;
         }

         return null;
}

9 二叉搜索树转化为排序的双向链表

二叉搜索树与双向链表

1)思路:

  • 中序遍历走到每一个节点

  • 更改每一个节点的前驱 和 后继

    • 设置 一个静态变量prev 初始化为 null,保存上一个节点, 前驱 pCur.left = prev,
    • 同时递归到了 pCur 才能设置 非空prev的后继(即上一个未设置的后继 pCur.right ),prev.right = pCur
    • 当本次递归完成后,设置 prev = pCur,继续递归 root.right;
  • 得到链表后,循环 pRootOfTree

    • 指向前一个节点 直到节点前驱为 null

2)解法:

public TreeNode pre = null;
public void ConvertChild(TreeNode root){
    if(root == null) return;
	
    //中序遍历的模式,先遍历左节点,再进行操作
    ConvertChild(root.left);
    root.left = pre;

    if(pre != null){
        pre.right = root;
    }

    pre = root;
    //针对一个节点操作结束后,再进入右节点遍历
    ConvertChild(root.right);
}

public TreeNode Convert(TreeNode pRootOfTree) {


    if(pRootOfTree == null) return null;
    ConvertChild(pRootOfTree);

    //此时得到的链表后,要找到节点前驱为空的表头
    TreeNode head = pRootOfTree;
    while(head.left != null){
        head = head.left;
    }

    return head;
}

10 根据先序中序遍历序列构造二叉树历

105. 从前序与中序遍历序列构造二叉树

中序遍历是左 根 右,前序遍历是根 左 右,我们可以通过前序序列的下标从左到右的根节点,到中序序列中寻找到对应的根节点,中序序列根节点的左边表示左树,右边表示右树,一步步将前序序列下标向后,即可构建起一颗树

1)思路:

(1)TreeNode buildTreeChild(int[] preorder, int[] inorder, int inbegin, int inend)

  • 子问题思路,递归创建树

  • 中止条件 inbegin > inend

  • findRootIndex寻找根节点在inorder的下标

  • 设置 成员变量 prIndex 遍历preoder

    • 如果设置成局部变量,在将左树创建完成后,但是prindex指向的还是preorder的第二个元素。
  • 创建左右子节点进行递归

  • 返回根节点

(2)int findRootIndex(int[] inoder, int inbegin, int inend, int key)

  • 在中序遍历数组中**找到key的下标**

(3)buildTree(int[] preorder, int[] inorder)

  • 调用buildTreeChild 返回根节点

2)解法:

  • buildTree
public TreeNode buildTree(int[] preorder, int[] inorder) {
    if(preorder == null || inorder == null) return null;
    return buildTreeChild(preorder, inorder, 0, inorder.length - 1);
}
  • buildTreeChild
public int preIndex = 0;
public TreeNode buildTreeChild(int[] preorder, int[] inorder,