“手撕”二叉树的OJ习题

故事的开头,我们先来三道不是oj的开胃菜,练练手感,后面9道都是OJ题。

目录

第一题

第二题

第三题

第四题

第五题

第六题

第七题 

第八题

第九题

第十题

第十一题 


第一题

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

 首先我们需要一个栈来存放二叉树里面的元素,定义一个Tree Node类型的cur来指向要入栈的元素,然后一直往栈里放root.left,边放边打印,全部放完就出栈。最后让cur指向栈顶元素,也就是回退到不为空的节点,再遍历right。!stack.isEmpty()就是栈里面不为空,就不用再写一遍while的打印循环了。

public void preOrderNot(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }

第二题

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

这也是同上面那一道题一样,但是要注意的就是,要先遍历完全部的left再打印,而前序遍历是边遍历边打印。 

    public void inOrderNot(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) return;
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            System.out.print(top.val + " ");
            cur = top.right;
        }
    }

第三题

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

这道题稍微会比上面两道复杂一点,但是大致思路也是一样的。如果完全按照上面两道题的思路就会陷入死循环。这里遇到空,栈顶top不能直接pop,需要peek看一下 ,因为一删就没有了,找不到了,后序遍历还没有打印这个节点,得左右都打印完才能打印。所以需要看看right有没有元素。跟着代码就会死循环,所以需要定义一个prev表示如果打印过了,就不再循环,退回上一个元素,就不会死循环了。

public void postOrderNot(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        TreeNode prev=null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            //第二个条件说明被打印过了,直接弹出他的父亲并打印
            if (top.right == null||prev==top.right) {
                stack.pop();
                System.out.print(top.val + " ");
                prev=top;
            } else {
                cur = top.right;
            }
        }
    }

第四题

检查两颗树是否相同。 OJ链接

 这道题非常简单,从结构上开始考虑,如果两个为空,为true;一个为空一个不为空,结构长得都不一样所以false,两个都不为空,这时候才开始判断他们的值一不一样,不一样false,一样的话继续递归。

public boolean isSameTree(TreeNode p, TreeNode q) {
        // 两个为空
        if (p == null && q == null) {
            return true;
        }//一个为空一个不为空
        if (p == null && q != null) {
            return false;
        }
        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);
    }

第五题

 另一颗树的子树。OJ链接

也是通过结构判断,要判断的树为空直接false;从最初的根开始就一样了, true;左子树和子树一样,true;右子树一样也是true;不然就是false。

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

第六题

 翻转二叉树。OJ链接

树为空,不能翻转,返回null 。定义一个tmp来作为中间媒介交换左和右的元素,由于父亲被带过去了,所以孩子也会一整个被搬过去,不用担心递归时子类的左右树不匹配。然后再把左子树和右子树都进行递归,最后返回根节点。

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

第七题 

 判断一颗二叉树是否是平衡二叉树。OJ链接

什么是平衡二叉树?就是左子树和右子树高度差必须小于等于1。左子树如果树为空,平衡true;定义左高度和右高度,用getHeight方法获取左右树的高度,然后用绝对值方法abs来求高度差,只要左子树和右子树高度差小于1,并且左子树自己平衡,右子树也平衡才true。

public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }int leftH=getHeight(root.left);
        int rightH=getHeight(root.right);
        return Math.abs(leftH-rightH)<=1&&
                isBalanced(root.left)&&
                isBalanced(root.right);
    }
    // 获取二叉树的高度
    public int getHeight(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftH=getHeight(root.left);
        int rightH=getHeight(root.right);
        return Math.max(leftH,rightH)+1;
    }

第八题

对称二叉树。 OJ链接

如果root==null则是true,书写一个检测子树对不对称的方法,然后判断结构,如果左子树为空,右子树不为空,或者右子树为空,左子树不为空,则结构不同,false;如果两个都为空,则返回true;如果两个都不为空,则判断他们的值,不一样就false,一样的话就继续递归。

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

    public boolean isSymmetricchild(TreeNode leftTree, TreeNode rightTree) {
        if (leftTree != null && rightTree == null || leftTree == null && rightTree != null) {
            return false;
        }
        if (leftTree == null && rightTree == null) {
            return true;
        }
        if (leftTree.val != rightTree.val) {
            return false;
        }
        return isSymmetricchild(leftTree.left, rightTree.right) &&
                isSymmetricchild(leftTree.right, rightTree.left);
    }

第九题

 二叉树的构建及遍历。OJ链接

 利用i++,遍历一个字符串,charAt获取每个元素,如果不为“#”则直接new TreeNode(charAt(i))进去接到root后面,是的话就i++;问题来了,new了不就重新创建TreeNode了吗,不会把之前的替换掉吗?不会,因为需要在后面的代码写上root.leftheroot.right递归下去,new出来的root直接接到left和right上面了。

    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 creatTree(String str) {
            TreeNode root = null;
            if (str.charAt(i) != '#') {
                root = new TreeNode(str.charAt(i));
                i++;
                root.left = creatTree(str);
                root.right = creatTree(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);
            // 注意 hasNext 和 hasNextLine 的区别
            while (in.hasNextLine()) { // 注意 while 处理多个 case
                String str = in.nextLine();
                TreeNode root = creatTree(str);
                inOrder(root);
            }
        }
    }

第十题

 二叉树的分层遍历 。OJ链接

利用队列在装这些元素,如果root=null直接返回。不为空,则入队一个root,队列不为空的话把这个打印出来,出队,如果这个root左右子树不为空,入队,然后进行循环,直到一整颗树被打印完。为什么用队列而不用栈呢?如果用栈就从 右往左打印了,显然不符合层序遍历的规律。

public void levelOrder(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        if(root==null){
            return;
        }
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.print(cur.val+" ");
            if(cur.left!=null){
                queue.offer(cur.left);
            }if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }

第十一题 

 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 。OJ链接

也是利用结构判断,如果root=null,返回null;如果p和q任意有个人在root,直接返回root;如果没有,继续递归,看看左右子树:如果左右子树都找得到p或q,那么说明左右子树各有一个,它的祖先必然是root;如果都在左子树,找到一个就返回,都在右子树,找到一个就返回。 

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        if(root==p||root==q){
            return root;
        }
        TreeNode leftTree=lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree=lowestCommonAncestor(root.right,p,q);
        //左子树和右子树各一个
        if(leftTree!=null&&rightTree!=null){
            return root;
        }
        //都在左子树,找到一个就返回
        else if(leftTree!=null){
            return leftTree;
        }//都在右子树,找到一个就返回
        else{
            return rightTree;
        }
    }

相关推荐

  1. OJ习题

    2024-06-12 08:02:05       7 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-06-12 08:02:05       18 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-06-12 08:02:05       19 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-06-12 08:02:05       18 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-06-12 08:02:05       20 阅读

热门阅读

  1. jQuery Ajax 基本用法 附带Fetch API

    2024-06-12 08:02:05       7 阅读
  2. cd和pwd命令

    2024-06-12 08:02:05       3 阅读
  3. Date类

    2024-06-12 08:02:05       5 阅读
  4. LINUX

    LINUX

    2024-06-12 08:02:05      6 阅读
  5. Mongodb学习

    2024-06-12 08:02:05       8 阅读
  6. 【每日一题】01

    2024-06-12 08:02:05       6 阅读
  7. MYSQL execute command denied to user ‘‘@‘%‘ for routine

    2024-06-12 08:02:05       7 阅读
  8. 【SpringBoot】理解Spring Boot自动配置的底层原理

    2024-06-12 08:02:05       6 阅读
  9. CentOS Linux Yum Docker安装与升级

    2024-06-12 08:02:05       7 阅读
  10. 如何应付忘记Console口密码

    2024-06-12 08:02:05       5 阅读
  11. spring和mybatis中的连接池和缓存

    2024-06-12 08:02:05       5 阅读
  12. ubuntu 22.04 升级到24.04

    2024-06-12 08:02:05       6 阅读