欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树镜像问题

程序员文章站 2022-03-11 17:46:47
...

今天写了剑指offer中的二叉树镜像问题,写到第三种解法的时候遇到了一个关于ArrayDeque的问题,将其记录下来
二叉树镜像问题
思路:镜像就是将“根”节点的左右两个“子”节点互换
解法一:

/**
     * 递归
     * @param root
     */
    public static void Mirror1(TreeNode root) {
        if(root == null || (root.left == null&&root.right == null))return;
        TreeNode pTree = root.left;
        root.left = root.right;
        root.right = pTree;
        Mirror1(root.left);
        Mirror1(root.right);
    }

解法二:

/**
     * 二叉树深度搜索
     * @param root
     */
    public static void Mirror2(TreeNode root) {
        if(root == null || (root.left == null&&root.right == null))return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode pTree,curTree;
        while (!stack.isEmpty()) {
            curTree = stack.pop();
            if(curTree == null || (curTree.left == null&&curTree.right == null))continue;
            pTree = curTree.left;
            curTree.left = curTree.right;
            curTree.right = pTree;
            stack.push(curTree.left);
            stack.push(curTree.right);
        }
    }

解法三:

  /**
     * 二叉树广度搜索
     * @param root
     */
    public static void Mirror3(TreeNode root) {
        if(root == null || (root.left == null&&root.right == null))return;
        Queue<TreeNode> queue = new LinkedList<>();
        //Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root); 
        TreeNode pTree, curTree;
        while(!queue.isEmpty()) {
            curTree = queue.poll();
            if(curTree == null || (curTree.left == null&&curTree.right == null))continue;
            pTree = curTree.left;
            curTree.left = curTree.right;
            curTree.right = pTree;
            queue.add(curTree.left);
            queue.add(curTree.right);
        }
    }

解法三我创建了一个队列 Queue queue = new ArrayDeque<>();然后提交直接报了空指针异常,看了一下源码才知道ArrayDeque中的add方法调用了addLast方法,addLast会判断一下传进来的参数是否为空,为空直接抛出空指针异常,下面为add和addLast的源码

    public boolean add(E e) {
        addLast(e);
        return true;
    }
public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }
相关标签: 学习记录