Java-数据结构-二叉树习题(1)

对于二叉树的学习，主要的还是得多多练习~毕竟二叉树属于新的知识，并且也并不是线性结构，再加上经常使用递归的方法解决二叉树的问题，所以代码的具体流程还是无法看到的，只能通过画图+想象，所以还是必须多加练习，使自己见识的题型更多，才会熟能生巧~

第一题、相同的树

📚 思路提示：

这一题还是很好想的~，对于比较两个相同的树，我们只需要像之前模拟实现二叉树的方法一样，将它拆解成 " 左子树和右子树的子问题 " 将两个树的左子树与左子树进行比较，右子树与右子树进行比较。

并且再通过递归的方式，不断对子树再次执行 " 拆解成新的左子树和右子树 比较对应子树是否相同 "的操作。

直到从最底层的子树(叶子结点)递归回到两个数的根节点时，如果中途出现过 false 那么返回的就是 false ，反之则返回 true。

而其中结点的比较过程，需要判断的问题有这几种：

📕 如果 p == null 并且 q == null 则代表同时达到叶子节点，返回 true 

📕 如果 p 和 q 没有进入上述判断语句，并且此时 p == null 或者 q == null 则代表有一方提前访问到了子树，则代表两棵子树的长度不相同，返回 false

📕 如果 p 和 q 都没进入上述两个判断语句，那么此时 p 和 q 都不为 null ，此时正常对它们的值进行比较，如果 p.val 不等于 q.val 则返回false

📕 最后递归函数，两次函数传参 " (p.left，q.left) && (p.right，q.right) "，只有全 true 的时候，才能最后返回 true 

⭐ 图示：

📖 代码示例：

class Solution {
    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); 
    } 
}

第二题、另一棵树的子树

📚 思路提示：

对于此题，其实就是上一题的引申~我们想要判断，一棵树是否是另一棵树的子树，那么我们首先要在另一棵树中找到这棵树的根节点

找到根节点后，我们就可以对这棵树进行判断啦~没错的，也就是判断它是否为相同的树，那么我们直接使用上一题的方法即可，首先找到根节点，然后再调用"判断是否为相同树"的方法进行递归即可

那么如何找到这个根结点呢？有以下的步骤：

📕 不断递归该方法，分别传参判断(root.left)和(root.right)，与subRoot的根节点是否相同(直接通过判断两棵树是否相等的方法即可)

📕 如果 root 等于 null 则返回 false 代表该子树中没找到那棵相同子树，退出递归

📕 如果"两树相同方法返回了true"，则返回 true，代表该子树中找到了那棵相同子树，退出递归 

⭐ 图示：

📖 代码示例：

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

第三题、翻转二叉树

想要翻转二叉树，就需要我们对树进行遍历，所以该题有多种解法，取决于它采用何种遍历。

(需要注意的是，不是将根节点下的左右子树翻转就好了，而是需要每棵树的子树都要进行翻转)

📚 思路提示[前/中/后序遍历]：

还是很简单的思路，只需要不断的递归函数，再将其中的结点互换即可~这里就不再过多赘述啦~我们直接看图片

⭐ 图示[前/中/后序遍历](1)：

📖 代码示例(1)：

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

上述方法是通过借助中间变量 tmp 来实现的，接下来我们不用 tmp，而是将左右子树两个结点存储，再递归回去分别进行交换。

⭐ 图示[前/中/后序遍历](2)：

📖 代码示例(2)：

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

📚 思路提示[层序遍历]：

层序遍历，在上一篇博客中我们已经讲解到了~就是将每一层的结点按照从左至右，从上至下的顺序存储到队列中，并且通过循环，将队列中的元素(一层的结点)依次出队列打印出来。

而在这题中，我们只需要在结点出队列的时候，同时将每个结点的左右子结点进行互换即可~思路还是很简单的，我们直接看图看代码~~

⭐ 图示[层序遍历]：

📖 代码示例(3)：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.push(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.removeLast();
            if (node.left != null) {
                deque.push(node.left);
            }
            if (node.right != null) {
                deque.push(node.right);
            }
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return root;
    }
}

第四题、反转二叉树的奇数层

我们之所以先讲了一个翻转二叉树，其实目的就是引出这道题~至于这道题应该怎么求解，其实也是换汤不换药，在这里我们提供两种解法：

📕 层序排列

📚 思路提示(1)：

经过上面的那道题，相信大家对层序遍历也有了比较深刻的理解了~而对于这道题也并不难，上面的代码要求我们将所有层的左右结点都进行翻转，这题则是将奇数层的左右结点进行翻转。

所以我们只需要在循环外部定义一个变量，通过这个变量来记录每次遍历时队列中计入结点对应为第几层，再将奇数层的结点相互调换即可~

使用该方法解题有以下几点需要注意：

📕 注意题中的根节点层数是以0开始的，而并非是1

📕 外层while循环不能再像上一题一样，每出队一个结点(及子树)，就判断一次while循环，这样就无法获取层数

📕 而想修改上述问题，我们就需要在while循环内部再设置一个循环，我们定义此时的队列元素个数为len，定义条件while(len-- > 0)，并且将入队列和出队列的操作都在这个循环内部进行，这样就能解决查找层数不准确的问题了。

📕 同时，如果我们想做到上述，在一次while大循环中解决多次结点入队列出队列，那么对应的，我们也要同时应对交换结点这一步，我这里采用的方法是"当层数为奇数时，将队列中结点存入一个顺序表中，通过双指针的方法，将其中结点值进行翻转"~注意，这里不推荐使用链表，因为速度的消耗极大：

顺序表：

链表：

⭐ 图示(1)：

📖 代码示例(1)：

class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        if (root == null) {
            return null;
        }
        int num = 0;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.push(root);
        while (!deque.isEmpty()) {
            int len = deque.size();
            if (num % 2 != 0) {
                List<TreeNode> list = new ArrayList<>(deque);
                for (int i = 0, j = list.size() - 1; i < j; i++, j--) {
                    TreeNode tmpl = list.get(i);
                    TreeNode tmpr = list.get(j);
                    int tmp = tmpl.val;
                    tmpl.val = tmpr.val;
                    tmpr.val = tmp;
                }
            }
            while(len-- > 0){
                TreeNode node = deque.removeLast();
                if (node.left != null) {
                    deque.push(node.left);
                }
                if (node.right != null) {
                    deque.push(node.right);
                }
            }
            num++;
        }
        return root;
    }
}

📕 分解子树法

📚 思路提示(2)：

这种解法相对于上一种解法就要简单许多了，同时效率也达到了显著的提升~既不用队列，也不用顺序表，更用不上循环交换节点的值！~

果然树还是得用递归呀~

其实还是很好理解的，平时我们进行结点的交换，只是传入root的左结点和右结点，就能够通过递归将所有结点都互换

那么我们只需要创建一个方法，使它的参数再多一个int类型，每次递归都在它的原基础上+1，那么就可以很清晰的分辨出是奇数层还是偶数层

至于过程也就是和平时的翻转结点多了个判断层数的步骤，这里就不再过多的画图赘述啦~我们直接看代码，包看得懂的。

📖 代码示例(2)：

class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        if (root == null) {
            return null;
        }
        move(root.left, root.right, 1);
        return root;
    }
    public void move(TreeNode left, TreeNode right, int num) {
        if(left == null || right == null){
            return;
        }
        if (num % 2 != 0) {
            int tmp = left.val;
            left.val = right.val;
            right.val = tmp;
        }
        move(left.left, right.right, num + 1);
        move(left.right, right.left, num + 1);
    }
}

那么这次关于二叉树的习题相关知识，就为大家分享到这里啦，作者能力有限，如果有讲得不清晰或者不正确的地方，还请大家在评论区多多指出，我也会虚心学习的！那我们下次再见哦

原文地址：https://blog.csdn.net/ixiaotang_/article/details/145197782

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！