[数据结构与算法] 笔试面试高频考点 12道经典题目带你走进二叉树（2）—

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 笔试面试高频考点 12道经典题目带你走进二叉树（2）——数据结构 -> 正文阅读

[数据结构与算法]笔试面试高频考点 12道经典题目带你走进二叉树（2）——数据结构

题目：

判断一棵树是不是完全二叉树
求出二叉树的最大宽度
检查两颗树是否相同
判断一颗二叉树是否是平衡二叉树
判断是否是对称二叉树
二叉树改为镜像二叉树
二叉树的构建和遍历
找到该二叉树中两个指定节点的最近公共祖先
二叉搜索树转化为排序的双向链表
根据先序中序遍历序列构造二叉树历
根据中序后序遍历序列构造二叉树
二叉树创建字符串

前言：

? 上一篇文章我们介绍了有关树和二叉树的基本概念知识及简单的二叉树基本操作，本篇文章紧接上集通过 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<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, int inbegin, int inend){
    if(inbegin > inend) return null;

    //构建根节点
    TreeNode root = new TreeNode(preorder[preIndex]);

    //在中序遍历数组中找到根节点下标
    int rootIndex = findRootIndex(inorder, inbegin, inend, preorder[preIndex]);
    //找到根节点过后，前序遍历数组中下标移向下一个元素
    preIndex++;

    //根据根节点下标 左右分开构建左、右树
    root.left = buildTreeChild(preorder, inorder, inbegin, rootIndex - 1);

    root.right = buildTreeChild(preorder, inorder, rootIndex + 1, inend);

    return root;

}

findRootIndex

public int findRootIndex(int[] inorder, int inbegin, int inend, int val){
    for(int i = inbegin; i <= inend; i++){
        if(inorder[i] == val) return i;
    }

    return -1;
}

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

106. 从中序与后序遍历序列构造二叉树

同前序中序构造的思路相同，只不过后序遍历序列的下标是从右向左，构建树是先构建根节点的右树再构建左树，因为从右到左找到根节点后，下一个下标代表的是右树的根节点。

1）思路：

注意左树是从递归的左边界是inbegin 不是0
从后序遍历数组从**后向前找根节点，先创建右树再创建左树**
- postIndex = postorder.length - 1；
- 注意树边界，root.right = buildTreeChild(postorder, inorder, rootIndex + 1, inend)
- 注意树边界，root.left = buildTreeChild(postorder, inorder, inbegin, rootIndex - 1)

2）解法：

buildTree

public TreeNode buildTree(int[] inorder, int[] postorder) {
    if(postorder == null || inorder == null) return null;
    //初始化postIndex为数组长度-1
    postIndex = postorder.length - 1;
    return buildTreeChild(postorder, inorder, 0, inorder.length - 1);
}

buildTreeChild

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

    int rootIndex = findRootIndex(inorder, inbegin, inend, postorder[postIndex]);
    postIndex--;

    //先构建右树
    root.right = buildTreeChild(postorder, inorder, rootIndex + 1, inend);

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

    return root;

}

findRootIndex

public int findRootIndex(int[] inorder, int inbegin, int inend, int val){
    for(int i = inbegin; i <= inend; i++){
        if(inorder[i] == val) return i;
    }

    return -1;
}

12 二叉树创建字符串

606. 根据二叉树创建字符串

1）思路：

前序遍历
判断t.left 是否为空
- 空，判断t.right 是否为空。 right为空return；right非空append( “()” )
- 非空，append( “(” )，tree2strChild(t.left, sb)，append( “)” )
判断t.right 是否为空
- 空return
- 非空，append( “(” )，tree2strChild(t.right, sb)，append( “)” )

2）解法：

public StringBuilder str = new StringBuilder();
public String tree2str(TreeNode root) {
    if(root == null) return null;
    str.append(root.val +"");

    if(root.left != null){
        str.append("(");
        tree2str(root.left);
        str.append(")");
    }else{
        if(root.right == null){
            return str.toString();
        }else{
            str.append("()");
        }
    }

    if(root.right != null){
        str.append("(");
        tree2str(root.right);
        str.append(")");
    }else{
        return str.toString();
    }

    return str.toString();
}