目录二叉树的遍历前序遍历中序遍历后序遍历层次遍历基础算法求二叉树中的节点个数求二叉树的深度（高度）求二叉树第k层的节点个数求二叉树中叶子节点的个数判断两棵二叉树是否相同的树判断二叉树是不是平衡二叉树求二叉树的镜像判断两个二叉树是否互相镜像判断是否为二分查找树BST本文的实例代码基于JAVA编写首先给出节点的数据结构publi...
大家好，我是架构君，一个会写代码吟诗的架构师。今天说一说二叉树算法题汇总「建议收藏」,希望能够帮助大家进步!!!
目录
本文的实例代码基于JAVA编写
首先给出节点的数据结构
<pre class="has">`public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
pre>
只听到从架构师办公室传来架构君的声音:
画桥流水东。有谁来对上联或下联?
二叉树的遍历前序遍历
题目参考（144）
递归解法：
<pre class="has">此代码由Java架构师必看网-架构君整理 `List list = new ArrayList();
public List preorderTraversal(TreeNode root) {
if (root != null) {
list.add(root.val);
if (root.left != null) {
preorderTraversal(root.left);
}
if (root.right != null) {
preorderTraversal(root.right);
}
}
return list;
pre>
非递归
<pre class="has">`List list = new ArrayList();
public List preorderTraversal(TreeNode root) {
Stack stack = new Stack();
while (root != null || !stack.isEmpty()) {
while (root != null) {
list.add(root.val);
stack.add(root);
root = root.left;
}
if (!stack.isEmpty()) {
TreeNode node = stack.pop();
root = node.right;
}
}
return list;
pre>
中序遍历
题目参考（94）
递归解法：
<pre class="has">此代码由Java架构师必看网-架构君整理 `List list = new ArrayList();
public List inorderTraversal(TreeNode root) {
if (root != null) {
if (root.left != null) {
inorderTraversal(root.left);
}
list.add(root.val);
if (root.right != null) {
inorderTraversal(root.right);
}
}
return list;
pre>
非递归解法：用栈先把根节点的所有左孩子都添加到栈内，然后输出栈顶元素，再处理栈顶元素的右子树。
<pre class="has">`List list = new ArrayList();
public List inorderTraversal(TreeNode root) {
Stack stack = new Stack();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.add(root);
root = root.left;
}
if (!stack.isEmpty()) {
root = stack.pop();
list.add(root.val);
root = root.right;
}
}
return list;
pre>
后序遍历
题目参考（145）
递归解法：
<pre class="has">`List list = new ArrayList();
public List postorderTraversal(TreeNode root) {
if (root != null) {
if (root.left != null) {
postorderTraversal(root.left);
}
if (root.right != null) {
postorderTraversal(root.right);
}
list.add(root.val);
}
return list;
pre>
非递归解法：双栈法。
<pre class="has">`List list = new ArrayList();
public List postorderTraversal(TreeNode root) {
Stack stack1 = new Stack();
Stack stack2 = new Stack();
if (root != null) {
stack1.add(root);
}
while (!stack1.isEmpty()) {
TreeNode node = stack1.pop();
stack2.add(node);
if (node.left != null) {
stack1.add(node.left);
}
if (node.right != null) {
stack1.add(node.right);
}
}
while (!stack2.isEmpty()) {
list.add(stack2.pop().val);
}
return list;
pre>
层次遍历
思路：分层遍历二叉树（按层次从上到下，从左到右）迭代Java模拟求二叉树中的节点个数求的深度（高度），相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点，访问，若左子节点或右子节点不为空，将其压入队列。
<pre class="has">`public static void levelTraversal(TreeNode root){
if(root == null) {
return;
}
Queue queue = new LinkedList(); // 对列保存树节点
queue.add(root);
while (!queue.isEmpty()) {
TreeNode temp = queue.poll();
System.out.print(temp.val + "->");
if (temp.left != null) { // 添加左右子节点到对列
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
}
pre>
变形：按层保存，题目参考（102）
<pre class="has">`public List levelOrder(TreeNode root) {
List list = new ArrayList();
Queue queue = new LinkedList();
if (root != null) {
queue.add(root);
}
while (!queue.isEmpty()) {
int size = queue.size();
List l = new ArrayList();
while (size > 0) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.add(node.left);
l.add(node.left.val);
}
if (node.right != null) {
queue.add(node.right);
l.add(node.right.val);
}
size--;
}
list.add(l);
}
return list;
pre>
基础算法求二叉树中的节点个数
递归解法：O(n)O(n)
<pre class="has">`public static int getNodeNumRec(TreeNode root) {
if (root == null) {
return 0;
}
return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1;
pre>
非递归解法：O(n)O(n)。基本思想同。即用一个Queue，在Java里面可以用来模拟
<pre class="has">`public static int getNodeNum(TreeNode root) {
if (root == null) {
return 0;
}
Queue queue = new LinkedList(); // 用队列保存树节点，先进先出
queue.add(root);
int count = 1; // 节点数量
while (!queue.isEmpty()) {
TreeNode temp = queue.poll(); // 每次从对列中删除节点，并返回该节点信息
if (temp.left != null) { // 添加左子孩子到对列
queue.add(temp.left);
count++;
}
if (temp.right != null) { // 添加右子孩子到对列
queue.add(temp.right);
count++;
}
}
return count;
pre>
求二叉树的深度（高度）
题目参考（104）
递归解法：O(n)O(n)
<pre class="has">`public int maxDepth(TreeNode root) {
int d = 0;
if (root == null) {
return 0;
}
d = Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
return d;
pre>
非递归解法：O(n)O(n)。基本思想同。即用一个Queue，在Java里面可以用来模拟。
<pre class="has">`public static int getDepth(TreeNode root) {
if (root == null) {
return 0;
}
int currentLevelCount = 1; // 当前层的节点数量
int nextLevelCount = 0; // 下一层节点数量
int depth = 0; // 树的深度
Queue queue = new LinkedList(); // 对列保存树节点
queue.add(root);
while (!queue.isEmpty()) {
TreeNode temp = queue.remove(); // 移除节点
currentLevelCount--; // 当前层节点数减1
if (temp.left != null) { // 添加左节点并更新下一层节点个数
queue.add(temp.left);
nextLevelCount++;
}
if (temp.right != null) { // 添加右节点并更新下一层节点个数
queue.add(temp.right);
nextLevelCount++;
}
if (currentLevelCount == 0) { // 如果是该层的最后一个节点，树的深度加1
depth++;
currentLevelCount = nextLevelCount; // 更新当前层节点数量并且重置下一层节点数量
nextLevelCount = 0;
}
}
return depth;
pre>
求二叉树第k层的节点个数
递归解法： O(n)O(n)
思路：求以root为根的k层节点数目，等价于求以root左孩子为根的k-1层（因为少了root）节点数目 加上以root右孩子为根的k-1层（因为 少了root）节点数目。即：
如果二叉树为空或者k 如果二叉树不为空并且k==1，返回1
如果二叉树不为空且k>1二叉树遍历算法 java，返回root左子树中k-1层的节点个数与root右子树k-1层节点个数之和
<pre class="has">`public static int getNodeNumKthLevelRec(TreeNode root, int k) {
if (root == null || k < 1) {
return 0;
}
if (k == 1) {
return 1;
}
return getNodeNumKthLevelRec(root.left, k - 1) + getNodeNumKthLevelRec(root.right, k - 1);
pre>
求二叉树中叶子节点的个数
递归解法：
<pre class="has">`public static int getNodeNumLeafRec(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
return getNodeNumLeafRec(root.left) + getNodeNumLeafRec(root.right);
pre>
非递归解法：基于层次遍历进行求解，利用Queue进行。
判断两棵二叉树是否相同的树
递归解法：
<pre class="has">`public static boolean isSameRec(TreeNode r1, TreeNode r2) {
if (r1 == null && r2 == null) { // 都是空
return true;
} else if (r1 == null || r2 == null) { // 有一个为空，一个不为空
return false;
}
if (r1.val != r2.val) { // 两个不为空，但是值不相同
return false;
}
return isSameRec(r1.left, r2.left) && isSameRec(r1.right, r2.right); // 递归遍历左右子节点
pre>
非递归解法：利用Stack对两棵树对应位置上的节点进行判断是否相同。
<pre class="has">`public static boolean isSame(TreeNode r1, TreeNode r2){
if (r1 == null && r2 == null) { // 都是空
return true;
} else if (r1 == null || r2 == null) { // 有一个为空，一个不为空
return false;
}
Stack stack1 = new Stack();
Stack stack2 = new Stack();
stack1.add(r1);
stack2.add(r2);
while (!stack1.isEmpty() && !stack2.isEmpty()) {
TreeNode temp1 = stack1.pop();
TreeNode temp2 = stack2.pop();
if (temp1 == null && temp2 == null) { // 两个元素都为空，因为添加的时候没有对空节点做判断
continue;
} else if (temp1 != null && temp2 != null && temp1.val == temp2.val) {
stack1.push(temp1.left); // 相等则添加左右子节点判断
stack1.push(temp1.right);
stack2.push(temp2.left);
stack2.push(temp2.right);
} else {
return false;
}
}
return true;
pre>
判断二叉树是不是平衡二叉树
递归实现：借助前面实现好的求二叉树高度的函数
<pre class="has">`public static boolean isAVLTree(TreeNode root) {
if (root == null) {
return true;
}
if (Math.abs(getDepth(root.left) - getDepth(root.right)) > 1) { // 左右子树高度差大于1
return false;
}
return isAVLTree(root.left) && isAVLTree(root.right); // 递归判断左右子树
pre>
求二叉树的镜像
递归实现：破坏原来的树，把原来的树改成其镜像
<pre class="has">`public static TreeNode mirrorRec(TreeNode root) {
if (root == null) {
return root;
}
TreeNode left = mirrorRec(root.right); // 递归镜像左右子树
TreeNode right = mirrorRec(root.left);
root.left = left; // 更新根节点的左右子树为镜像后的树
root.right = right;
return root;
pre>
递归实现：不能破坏原来的树二叉树遍历算法 java，返回一个新的镜像树
<pre class="has">`public static TreeNode mirrorCopyRec(TreeNode root) {
if (root == null) {
return root;
}
TreeNode newRoot = new TreeNode(root.val); // 创建新节点，然后交换左右子树
newRoot.left = mirrorCopyRec(root.right);
newRoot.right = mirrorCopyRec(root.left);
return newRoot;
pre>
判断两个二叉树是否互相镜像
递归解法：与比较两棵二叉树是否相同解法一致（题5），非递归解法省略。
<pre class="has">`public static boolean isMirrorRec(TreeNode r1, TreeNode r2) {
if (r1 == null && r2 == null) {
return true;
} else if (r1 == null || r2 == null) {
return false;
}
if (r1.val != r2.val) {
return false;
}
// 递归比较r1的左子树的镜像是不是r2右子树
// 和r1的右子树的镜像是不是r2的左子树
return isMirrorRec(r1.left, r2.right) && isMirrorRec(r1.right, r2.left);
pre>
判断是否为二分查找树BST
题目参考（98）
递归解法：中序遍历的结果应该是递增的
<p><pre class="has">public static boolean isValidBST(TreeNode root, int pre){
if (root == null) {
return true;
}
boolean left = isValidBST(root.left, pre);
if (!left) {
return false;
}
if(root.val