点击上方“罗晓胜”，马上关注，您的支持对我帮助很大
/ 前言 /
二叉树（Binary tree）是树形结构的一个重要类型。
许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。
二叉树特点是每个节点最多只能有两棵子树，且有左右之分。
例：
1 2 3
/ 正文 /
反转二叉树（Invert a binary tree）
题目：
将二叉树的两个孩子换位置，即左变右，右变左。
解题思路：
方法一：循环，栈存储（DFS，非递归) 本质思想是，左右节点进行交换，循环翻转每个节点的左右子节点，将未翻转的子节点存入栈中，循环直到栈里所有节点都循环交换完为止。 方法二：循环，队列存储（BFS，非递归） 本质思想是，左右节点进行交换，循环翻转每个节点的左右子节点，将未翻转的子节点存入队列中，循环直到栈里所有节点都循环交换完为止。 方法三：递归 本质思想也是左右节点进行交换，交换前递归调用对根结点的左右节点分别进行处理，保证交换前左右节点已经翻转。
代码实现(栈实现)：
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
Stack stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {
final TreeNode node = stack.pop();
final TreeNode left = node.left;
node.left = node.right;
node.right = left;
if(node.left != null) {
stack.push(node.left);
}
if(node.right != null) {
stack.push(node.right);
}
}
return root;
}
队列实现
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
Queue queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
TreeNode left = node.left;
node.left = node.right;
node.right = left;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return root;
}
递归实现
public TreeNode invertTree(TreeNode node) {
if (node == null) {
return null;
}
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
invertTree(node.left);
invertTree(node.right);
return node;
}
重建二叉树
题目：
输入二叉树的前序遍历和中序遍历的结果,重建出该二叉树。
假设前序遍历和中序遍历结果中都不包含重复的数字,例如输入的前序遍历序列 {1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
重建出二叉树。
解题思路：
前序遍历第一个结点是父结点，中序遍历如果遍历到父结点，那么父结点前面的结点是左子树的结点，后边的结点的右子树的结点，这样我们可以找到左、右子树的前序遍历和中序遍历，我们可以用同样的方法去构建左右子树，可以用递归完成。
代码：
public class BinaryTreeNode {
public static int value;
public BinaryTreeNode leftNode;
public BinaryTreeNode rightNode;
}
public class Solution {
public static BinaryTreeNode constructCore(int[] preorder, int[] inorder) throws Exception {
if (preorder == null || inorder == null) {
return null;
}
if (preorder.length != inorder.length) {
throw new Exception("长度不一样，非法的输入");
}
BinaryTreeNode root = new BinaryTreeNode();
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == preorder[0]) {
root.value = inorder[i];
System.out.println(root.value);
root.leftNode = constructCore(Arrays.copyOfRange(preorder, 1, i + 1),
Arrays.copyOfRange(inorder, 0, i));
root.rightNode = constructCore(Arrays.copyOfRange(preorder, i + 1, preorder.length),
Arrays.copyOfRange(inorder, i + 1, inorder.length));
}
}
return root;
}
}
二叉树遍历
二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问依次且仅被访问一次。 四种遍历方式分别为：先序遍历、中序遍历、后序遍历、层序遍历。
正常的一个满节点，A：根节点、B：左节点、C：右节点，
- 前序顺序是ABC（根节点排最先，然后同级先左后右）；
- 中序顺序是BAC(先左后根最后右）；
- 后序顺序是BCA（先左后右最后根）。
例：
1
2 3
4 5 6 7
- 前序遍历结果：1 2 4 5 3 6 7
- 中序遍历结果：4 2 5 1 6 3 7
- 后序遍历结果：4 5 2 6 7 3 1
创建一个二叉树
遍历之前，我们首先介绍一下，如何创建一个二叉树，在这里用的是先建左树再建右树的方法。
首先要声明结点TreeNode类，代码如下：
public class TreeNode {
public int data;
public TreeNode leftChild;
public TreeNode rightChild;
public TreeNode(int data){
this.data = data;
}
}
再来创建一颗二叉树：
public static TreeNode createBinaryTree(LinkedList list){
TreeNode node = null;
if(list == null || list.isEmpty()){
return null;
}
Integer data = list.removeFirst();
if(data!=null){
node = new TreeNode(data);
node.leftChild = createBinaryTree(list);
node.rightChild = createBinaryTree(list);
}
return node;
}
上面创建的二叉树的单向二叉树，思考一下该如何改造。
创建一颗满二叉树：
public static TreeNode createCompleteTree(LinkedList list, int index) {
TreeNode newNode = null;
//保证index不会越界
if(index < list.size()){
newNode = new TreeNode(list.get(index));
newNode.leftChild = createCompleteTree(list, 2 * index + 1);
newNode.rightChild = createCompleteTree(list, 2 * index + 2);
}
return newNode;
}
...
//调用
TreeNode completeTree = createCompleteTree(list, 0);
生成满二叉树算法解析：
原始list：{1,2,3,4,5,6,7}
期望结果：
1
2 3
4 5 6 7
不难分析，index之间的对应关系：
Index=0 子节点Index：1 2
Index=1 子节点Index：3 4
Index=2 子节点Index：5 6
规律就是当节点Index为n时，子节点Index分别为2n+1、2n+2
前序遍历
实现代码如下：
public static void preOrderTraveral(TreeNode node){
if(node == null){
return;
}
System.out.print(node.data+" ");
preOrderTraveral(node.leftChild);
preOrderTraveral(node.rightChild);
}
中序遍历
再者就是中序遍历，所谓的中序遍历就是先访问左节点，再访问根节点，最后访问右节点，
public static void inOrderTraveral(TreeNode node){
if(node == null){
return;
}
inOrderTraveral(node.leftChild);
System.out.print(node.data+" ");
inOrderTraveral(node.rightChild);
}
后序遍历
最后就是后序遍历，所谓的后序遍历就是先访问左节点，再访问右节点，最后访问根节点。
实现代码如下：
public static void postOrderTraveral(TreeNode node){
if(node == null){
return;
}
postOrderTraveral(node.leftChild);
postOrderTraveral(node.rightChild);
System.out.print(node.data+" ");
}
层序遍历
层序遍历，即逐层地，从左到右访问所有节点
//调用
bfs(root, 0);
List> res = new ArrayList>();
public void bfs(TreeNode root, int depth) {
if (res.size() == depth){
res.add(new ArrayList());
}
//把一层上的节点存在同行数组中
res.get(depth).add(root.data);
//搜索子节点深度增1，左子节点
if (root.leftChild != null){
bfs(root.leftChild, depth + 1);
}
//搜索子节点深度增1，右子节点
if (root.rightChild != null){
bfs(root.rightChild, depth + 1);
}
}
前序遍历（非递归）
首先申请一个新的栈，记为stack； 声明一个结点treeNode，让其指向node结点； 如果treeNode的不为空，将treeNode的值打印，并将treeNode入栈，然后让treeNode指向treeNode的右结点； 重复步骤3，直到treenode为空； 然后出栈，让treeNode指向treeNode的右孩子； 重复步骤3，直到stack为空.
实现代码如下：
public static void preOrderTraveralWithStack(TreeNode node){
Stack stack = new Stack();
TreeNode treeNode = node;
while(treeNode!=null || !stack.isEmpty()){
//迭代访问节点的左孩子，并入栈
while(treeNode != null){
System.out.print(treeNode.data+" ");
stack.push(treeNode);
treeNode = treeNode.leftChild;
}
//如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
if(!stack.isEmpty()){
treeNode = stack.pop();
treeNode = treeNode.rightChild;
}
}
}
后序遍历（非递归）
private static void postOrder(TreeNoderoot) { Stack src = new Stack (); Stack res = new Stack (); src.push(root); while(!src.isEmpty()){ TreeNode p = src.pop(); res.push(p); if(p.left != null){ src.push(p.left); } if(p.right != null){ src.push(p.right); } } //输出最终后序遍历的结果 while(!res.isEmpty()){ System.out.print(res.pop().val + " "); } }
计算深度
private int caculateDepth(TreeNode node) {
int leftDepth,rightDepth;
if(node == null) return 0;
else {
leftDepth = caculateDepth(node.leftChild);
rightDepth = caculateDepth(node.rightChild);
if(leftDepth >= rightDepth) {
return leftDepth+1;
}else {
return rightDepth+1;
}
}
}
二叉树最大直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
思路： 无论如何，一个路径一定会有一个最近的公共父结点。
路径长度 = 这个父结点的左右子树深度和
我们只需要遍历所有结点的左右子树深度和，找到最大的那个值就可以了。
深度优先遍历，设定一个成员变量，记录最大的直径。
代码实现
class Solution {
int res = 0;
public int diameterOfBinaryTree(TreeNode root) {
if(root == null) return 0;
dep(root);
return res;
}
public int dep(TreeNode node){
if(node == null) return 0;
int L = dep(node.left);
int R = dep(node.right);
res = Math.max(res, L+R);
return Math.max(L, R) +1;
}
}
关注我的公众号，学习技术或投稿
长按上图，识别图中二维码即可关注
