一、二叉树的遍历

遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算的基础。

遍历二叉树的时候，如果没有进行某种约定，每个人都按照自己的方式遍历，得出的结果就比较混乱，如果按照某种规则进行约定，则每个人对于同一棵树的遍历结果肯定是相同的。

如果N代表根节点，L代表根节点的左子树，R代表根节点的右子树，则根据遍历根节点的先后次序有以下遍历方式：

1. NLR（前序遍历）：访问根节点、根的左子树、根的右子树。
2. LNR（中序遍历）：根的左子树，访问根节点，根的右子树。
3. LRN（后序遍历）：根的左子树，根的右子树，访问根节点。

---

二、二叉树的基本操作

2.1 常用接口

// 前序遍历
void preOrderTraversal(Node root);// 中序遍历
void inOrderTraversal(Node root);// 后序遍历
void postOrderTraversal(Node root);// 遍历思路-求结点个数
static int size = 0;
void getSize1(Node root);// 子问题思路-求结点个数
int getSize2(Node root);// 遍历思路-求叶子结点个数
static int leafSize = 0;
void getLeafSize1(Node root);// 子问题思路-求叶子结点个数
int getLeafSize2(Node root);// 子问题思路-求第 k 层结点个数
int getKLevelSize(Node root);// 获取二叉树的高度
int getHeight(Node root);// 查找 val 所在结点，没有找到返回 null
// 按照 根 -> 左子树 -> 右子树的顺序进行查找
// 一旦找到，立即返回，不需要继续在其他位置查找
Node find(Node root, int val);

2.2 实现代码

完整代码

import java.util.ArrayList;
import java.util.List;class Node{public char val;public Node left;public Node right;public Node(char val) {this.val = val;}
}public class TestBinaryTree {//使用穷举的方式创建一棵二叉树public Node createTree() {Node A = new Node('A');Node B = new Node('B');Node C = new Node('C');Node D = new Node('D');Node E = new Node('E');Node F = new Node('F');Node G = new Node('G');A.left = B;A.right = C;B.left = D;B.right = E;C.left = F;C.right = G;return A;}//前序遍历void preOrderTraversal(Node root) {if (root == null) return;System.out.print(root.val + " ");preOrderTraversal(root.left);preOrderTraversal(root.right);}//前序遍历，使用返回listpublic List<Character> preOrderTraversal1(Node root) {List<Character> cList = new LinkedList<>();if (root == null) return cList;cList.add(root.val);List<Character> leftList = preOrderTraversal1(root.left);cList.addAll(leftList);List<Character> rightList = preOrderTraversal1(root.right);cList.addAll(rightList);return cList;}//中序遍历void inOrderTraversal(Node root) {if (root == null) return;inOrderTraversal(root.left);System.out.print(root.val + " ");inOrderTraversal(root.right);}//后序遍历void postOrderTraversal(Node root) {if (root == null) return;postOrderTraversal(root.left);postOrderTraversal(root.right);System.out.print(root.val + " ");}//求结点个数 -遍历思路//把每个结点都遍历一次，size一次++static int size = 0;void getSize1(Node root) {if (root == null) return;size++;getSize1(root.left);getSize1(root.right);}//求结点个数 -子问题思路//只判断目前该结点root是否有值，左右子树交给递归解决。int getSize2(Node root) {if (root == null) return 0;int val = getSize2(root.left) + getSize2(root.right) + 1;return val;}//求叶子结点个数 -遍历思路//没有左右子树的结点是叶子结点，遍历每一个结点，统计叶子结点static int leafSize = 0;void getLeafSize1(Node root) {if (root == null) return;if (root.left == null && root.right == null) leafSize++;getLeafSize1(root.left);getLeafSize1(root.right);}//求叶子结点个数 -子问题思路//只判断该结点是否是叶子，其它结点交给递归判断。int getLeafSize2(Node root) {if (root == null) return 0;if (root.left == null && root.right == null) return 1;int val = getLeafSize2(root.left) + getLeafSize2(root.right);return val;}//求第K层节点个数//子问题思路 -使用递归计算左右子树的节点，然后相加。int getKLevelSize(Node root, int k) {if (root == null) {throw new RuntimeException("k大于二叉树层数 或 根节点为null");}if (k == 1) return 1;int val = getKLevelSize(root.left,k-1) + getKLevelSize(root.right, k-1);return val;}//求二叉树的高度//子问题思路 -通过递归求左右子树高度，最后相比 取高者+1.//每次遍历都是通过return里面的+1，对子树高度相加。//最后左右子树遍历完，二者对比，取高者+1.int getHeight(Node root) {if (root == null) return 0;int leftTree = getHeight(root.left);int rightTree = getHeight(root.right);return leftTree > rightTree ? (leftTree+1) : (rightTree+1);}//在root中找val值//子问题解决思路 - 只判断该节点是否是val，其它节点交给递归解决。//注意最后所有条件不符合，需要返回nullNode find(Node root, char val) {if (root == null) return null;if (root.val == val) return root;Node ret = find(root.left, val);if (ret != null) return ret;ret = find(root.right, val);if (ret != null) return ret;return null;}
}

测试类代码

public class Test01 {public static void main(String[] args) {TestBinaryTree tbt = new TestBinaryTree();Node root = tbt.createTree();tbt.preOrderTraversal(root);System.out.println();tbt.inOrderTraversal(root);System.out.println();tbt.postOrderTraversal(root);System.out.println();System.out.println("--------结点--------");tbt.getSize1(root);System.out.println(tbt.size);System.out.println(tbt.getSize2(root));System.out.println("--------叶子--------");tbt.getLeafSize1(root);System.out.println(tbt.leafSize);System.out.println(tbt.getLeafSize2(root));System.out.println("--------第k层结点个数--------");int kLevelSize = tbt.getKLevelSize1(root, 4);System.out.println(kLevelSize);System.out.println("--------求树的高度--------");System.out.println(tbt.getHeight(root));System.out.println("--------找到val值--------");try {System.out.println(tbt.findVal(root, '1').val);}catch (NullPointerException e) {System.out.println("不存在这个字符");e.printStackTrace();}}
}

---

三、基础面试题

3.1 二叉树的前序遍历

前序遍历是根左右，我们只需要把根输出，左右子树的数据交给递归解决即可。

//前序遍历void preOrderTraversal(Node root) {if (root == null) return;System.out.print(root.val + " ");preOrderTraversal(root.left);preOrderTraversal(root.right);}

3.2 二叉树的中序遍历

中序遍历是左根右，我们只需要把根输出，左右子树的数据交给递归解决即可。

//中序遍历void inOrderTraversal(Node root) {if (root == null) return;inOrderTraversal(root.left);System.out.print(root.val + " ");inOrderTraversal(root.right);}

3.3 二叉树的后序遍历

后序遍历是左右根，我们只需要把根输出，左右子树的数据交给递归解决即可。

//后序遍历void postOrderTraversal(Node root) {if (root == null) return;postOrderTraversal(root.left);postOrderTraversal(root.right);System.out.print(root.val + " ");}

3.4 检查两颗树是否相同

使用子问题思路解决.
判断根节点是否都为空；亦或是一个为空，一个不为空；节点的val是否相同。

    //判断两棵树是否相同 - 使用子问题思路解决//判断根节点：//  1.是否都是null；值是否相同；一个为空 一个不为空；（结构比较，值比较）//  2.结构相同，值相同。//其它节点交给递归解决。public boolean isSameTree(Node x, Node y) {if ((x == null && y != null) || (x != null && y == null)) {return false;}if (x == null && y == null) {return true;}if (x.val != y.val) {return false;}return isSameTree(x.left, y.left) && isSameTree(x.right, y.right);}

3.5 另一颗树的子树

判断是否是 root 这棵树的结构的一部分即可。
直接判断 subRoot 和 root 这两棵树的结构是否相同；不同就判断 root 的子树和 subRoot 是否相同。

    //判断sub是否是root的子树。//判断root是否null，subRoot是否和root相同//不同就递归判断下面的结构，是否和subRoot相同public boolean isSubtree(Node root, Node 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;}

3.6 二叉树最大深度

通过递归求左右子树高度，最后相比 取高者+1.

每次遍历都是通过return里面的+1，对子树高度相加。最后左右子树遍历完，二者对比，取高者+1.

    //判断二叉树的最大深度public int maxDepth(Node root) {if (root == null) return 0;int leftTree = maxDepth(root.left);int rightTree = maxDepth(root.right);return leftTree > rightTree ? (leftTree+1) : (rightTree+1);}

3.7 判断一颗二叉树是否是平衡二叉树

解法一：

    //判断该二叉树是否是平衡二叉树//判断根节点的左右子树是否平衡，算出左右高度相减绝对值小于等于1//接着继续计算左右子树的左右子树。public boolean isBalanced1(Node root) {if (root == null) return true;int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return Math.abs(leftHeight-rightHeight)<=1 && isBalanced1(root.left) && isBalanced1(root.right);}

解法二：

优化了每个节点求深度的过程。
在遍历二叉树结点的时候，顺便判断二叉树是否平衡，就不需要全部结点都遍历。

    //判断该二叉树是否是平衡二叉树 - O(N)解法//上一个解法，每个节点都需要去求深度，导致开销过大。//O(N)解法，能遍历节点的中途，判断这部分二叉树是否平衡，不需要全部节点都遍历。public int maxDepth2(Node root) {if (root == null) return 0;//递归判断左右子树的高度。int leftHeight = maxDepth2(root.left);int rightHeight = maxDepth2(root.right);//高度不可能是负数，负数表示不平衡if (leftHeight >= 0 && rightHeight >= 0 &&//条件成立，说明是平衡的结点Math.abs(rightHeight - leftHeight) <= 0) {//返回结点的最大左右子节点，+1加上自己这个结点。return Math.max(rightHeight, leftHeight) + 1;}else {return -1;}}public boolean isBalanced2(Node root) {return maxDepth2(root) >= 0;}

3.8 对称二叉树

判断二叉树是否左右对称，有五种情况针对树的结构和数值。

只需要把情况都罗列进去，使用 if 进行判断即可。

其它的结点交给递归处理。

    //对称二叉树public boolean isSymmetricChild(Node leftTree, Node rightTree) {//判断左右子树结构是否相同if (leftTree == null && rightTree != null ||leftTree != null && rightTree == null) {return false;}//判断左右子树是否为 nullif (leftTree == null && rightTree == null) {return true;}//判断左右子树数值是否相同if (leftTree.val != rightTree.val) {return false;}//左右对称，那么递归解决左树和右树是否对称。return isSymmetricChild(leftTree.left, rightTree.right) &&isSymmetricChild(leftTree.right, rightTree.left);}//针对不同情况：传递根节点 还是根的左右树public boolean isSymmetric(Node root) {if (root == null) return false;return isSymmetricChild(root.left, root.right);}