二叉树镜像问题
程序员文章站
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();
}
上一篇: php可以删除html标签内容吗
下一篇: ros机器人编程实践-将消息发布在话题上