剑指offer面试题19 二叉树的镜像

考察点

树的遍历

知识点

题目

分析
我们分析算法题目的思路基本上都是归纳法，即通过举一些普通的例子来推理出算法流程，而画图又是举例子的常用手段，比如针对树或者链表画画图，针对数字类的举一些数字的例子寻找规律，很快就能得到解决问题的方案。这道题目要求树的镜像，只要谈到树我们的思维就往那几个遍历上靠，前序遍历树的过程中交换非叶子结点的左子树和右子树就可以了。

public class BinaryTree {Node root;public BinaryTree() {this.root = null;}public void convertMirror(Node root) {if (root == null) {return;}if (root.leftChild != null && root.rightChild != null) {Node tmp = root.leftChild;root.leftChild = root.rightChild;root.rightChild = tmp;}convertMirror(root.leftChild);convertMirror(root.rightChild);}public void insertTree(int val) {if (this.root == null) {Node root = new Node(val);this.root = root;} else {insertChildTree(this.root,val);}}public void insertChildTree(Node node,int val) {if (node != null && val <= node.val) {if (node.leftChild == null) {node.leftChild = new Node(val);} else {insertChildTree(node.leftChild,val);}}if (node != null && val > node.val) {if (node.rightChild == null) {node.rightChild = new Node(val);} else {insertChildTree(node.rightChild,val);}}}public Node getRoot() {return this.root;}public void prePrint(Node node) {if (node == null) {return;}System.out.print(node.val + " ");prePrint(node.leftChild);prePrint(node.rightChild);}
}
public class Node{int val;Node leftChild;Node rightChild;public Node(int data) {this.val = data;this.leftChild = null;this.rightChild = null;}
}
public class Nineteen {public static void main(String[] args) {BinaryTree binaryTree = new BinaryTree();binaryTree.insertTree(8);binaryTree.insertTree(6);binaryTree.insertTree(10);binaryTree.insertTree(5);binaryTree.insertTree(7);binaryTree.insertTree(9);binaryTree.insertTree(11);binaryTree.prePrint(binaryTree.getRoot());System.out.println();binaryTree.convertMirror(binaryTree.getRoot());binaryTree.prePrint(binaryTree.getRoot());}
}