数据结构：二叉树—面试题（一）

1、相同的树

2、另一棵树的子树

3、翻转二叉树

4、平衡二叉树

5、对称二叉树

6、二叉树遍历

7、二叉树的分层遍历

1、相同的树

习题链接https://leetcode.cn/problems/same-tree/description/

描述：

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

解题思路

根据题意，他要我们判断这两棵树是否相同，我们知道要判断两棵树是否相同，就是要判断树的结构和对应结点的内容是否相同。

首先我们要来看，给我们的两棵树是否是一棵树有结点，一棵树没有结点，如果是这样的话，我们就认为这两棵树不相同，同时如果这两颗树的根节点都为空，那么我们就认为，这两棵树相同。

经历了这两个条件后，此时的这两颗树一定是都存在结点，这时我们在判断此时的根节点值是否相同，如果不同，就是不相同的树，如果相同，我们就继续往下走，判断对应的左子树和右子树是否相同，在递归的形势下，传入两棵树根的左边结点作为新的根节点，进行判断，同理右边也是一样。在这种情况下完成对两棵树的结构和内容的判断。

完整代码

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p != null && q == null || p == null && q != null){
            return false;
        }
        if(p == null && q ==null){
            return true;
        }

        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right ,q.right);
    }
}

2、另一棵树的子树

习题链接https://leetcode.cn/problems/subtree-of-another-tree/

描述：

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

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

解题思路

根据题意，他是要我们判断给出的两棵树中一棵是否为另一棵的子树，而这个子树是包含某个结点开始和他所有的后代的，这样来看其实就是判断一棵树的子树和他给出的另一棵树是否相同。（注意：如果两棵树从根节点开始就是相同的，我们也认为他符合题意）

首先，我们从根节点开始进行判断，我们要先判断我们的根节点是否为空，因为在下面我们是要有递归实现的总有一次我们会递归到为空的时候，这就代表我们此时的根节点为空,而我们要判断的subRoot这棵树却不为空，这就代表了以此时结点为根节点的树是和我们要判断的树是不同的，因此我们要返回false.而我们判断的方法就是我们上面写的题相同的树，因此我们将根节点传isSameTree进行判断。

当我们判断完根结点后我们要判断跟的左子树，因此我们要将根的左结点传入进行递归，判断完再判断右树，如果都不存在就返回false;

完整代码

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        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 || p != null && q == null){
            return false;
        }
        if(p == null && q == null){
            return true;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);

    }
}

3、翻转二叉树

习题链接https://leetcode.cn/problems/invert-binary-tree/description/

描述：给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

解题思路

根据图示我们能发现这道题就是让我们将根的左右结点进行交换，说到交换这就简单了，想必大家都理解，而他是要交换整棵树因此我们交换完根节点后，还要交换他左子树的结点和右子树的结点，因此我们可以利用递归传入根的左右结点，再继续往下找左右结点进行交换。

完整代码

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return root;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

4、平衡二叉树

习题链接https://leetcode.cn/problems/balanced-binary-tree/description/

描述：给定一个二叉树，判断它是否是平衡二叉树

解题思路

首先我们要先来了解什么是平衡二叉树，所谓平衡二叉树就是，一个根节点左边的长度和右边的长度的差值要小于等于1.

而根据对平衡二叉树的了解，我们发现我们应该去求他左子树和右子树的长度，让他们相减。

关于二叉树长度的计算我们再二叉树中已经进行了讲解，大家可以去看看。数据结构：二叉树

因为我们要判断整棵树是否为平衡二叉树，因此我们要从根结点判断是否为平衡二叉树，还要对子树的子树进行平衡二叉树的判断，如果都是平衡二叉树，我们就认为他是平衡二叉树，对于这样的判断我们就要用到递归的方式来进行了。

因此我们获得根结点的左右子树长度进行相减并且利用递归传入根的左结点和右结点进行子树的子树判断

完整代码

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        int leftMax = getH(root.left);
        int rightMax = getH(root.right);
        return Math.abs(leftMax - rightMax) <=1 && isBalanced(root.left) && isBalanced(root.right);

    }
    public int getH(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftH = getH(root.left);
        int rightH = getH(root.right);
        return Math.max(leftH,rightH)+1;
    }
}

5、对称二叉树

习题链接https://leetcode.cn/problems/symmetric-tree/description/

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

解题思路

这道题其实和我们第1题是相同的，我们还是判断是否相同，只是从两棵树的判断，到了一棵树左右子树的判断，当时我们要注意因为他要判断是否为镜像，因此，我们判断是否相同是要判断一棵子树的左边和另一棵子树的右边，一棵子树的右边和另一棵子树的左边是否结构相同内容相同

完整代码

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return isSameTree(root.left,root.right);
    }
     public boolean isSameTree(TreeNode p ,TreeNode q){
        if(p != null && q == null || p == null && q != null ){
            return false;
        }
        if(p == null && q == null){
            return true;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.right) && isSameTree(p.right,q.left);
     }
}

6、二叉树遍历

习题链接https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking

描述：

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述：

输入包括1行字符串，长度不超过100。

输出描述：

可能有多组测试数据，对于每组数据，输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。每个输出结果占一行。

解题思路

根据题意，我们知道他是要我们根据先序遍历，建立一棵二叉树，再输出二叉树的中序遍历。

首先我们要根据先序遍历创建二叉树，在创建二叉树前我们要创建结点，因为二叉树是由一个个结点形成的。

创建完结点后，我们就要创建二叉树，我们知道先序遍历的顺序是：根左右，因此我们要先创建完左子树再创建右子树，那么什么时候我们停止创建左子树呢？

停止的时刻其实是当我们遇到空树的时候，而先序遍历给我们的空树就是“#”，因此只要我们没遇到“#”，就创建左子树，并让先序遍历往下走，遇到“#”了我们就停止，但依然让先序遍历往下走，并返回到上面一层，去创建右子树。

当右子树也遇到“#”了，我们就停止创建二叉树，但依然让先序遍历往下走，并返回到上面一层，此时左右子树都走完了，再返回上一层，去创建右子树，在这样不断的递归和返回就成功创建了二叉树。

当我们创建完二叉树后，接下来就是用中序遍历去打印了（左根右）

完整代码

import java.util.Scanner;
class TreeNode{
    char val;
    TreeNode left;
    TreeNode right;
    public TreeNode(char val){
        this.val = val;
    } 
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
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 oread(TreeNode root){
        if(root == null){
            return;
        }
        oread(root.left);
        System.out.print(root.val + " ");
        oread(root.right);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
           String str = in.nextLine(); 
           TreeNode root = createTree(str);
           oread(root);
       }
    }
}

7、二叉树的分层遍历

习题链接https://leetcode.cn/problems/binary-tree-level-order-traversal/description/

描述：

给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。

解题思路

这道题就是让我将二叉树由层序遍历输出，而层序遍历的方式我们再上一篇二叉树是已经进行了讲解大家可以去看看，数据结构：二叉树

而这道虽然仍是以层序遍历输出，但是他输出要求是同一层的放到一起输出。

因此我们可以在层序遍历的基础上再创建一个链表curList，然后再计算次数队列的长度，根据长度决定出队的个数，并让出队的元素放到链表curList中，并将此时出队的元素左右结点放入队列中，当这个循环结束了就代表上一个队列为空了，再将curList的值放入到list链表中，然后利用循环再判断此时的队列，再创建一个新的curList，重复上面的操作，这样就实现了同一层的放到一起输出

完整代码

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            List<Integer> curList = new ArrayList<>();
            int size = q.size();
            while(size != 0){
                TreeNode cur = q.poll();
                curList.add(cur.val);
                if(cur.left != null){
                    q.offer(cur.left);
                }
                if(cur.right != null){
                    q.offer(cur.right);
                }
                size--;
            }
            list.add(curList); 
        }
        return list;
    }
}

好了。今天的分享就到这里了，还请大家多多关注，我们下一篇再见！