### 常见算法总结 - 二叉树篇

#### 1.计算一个给定二叉树的叶子节点数目。

``````public static int calculateTreeNodeNumber(TreeNode treeNode) {

if (treeNode == null) {
return 0;
}

return calculateTreeNodeNumber(treeNode.left) + calculateTreeNodeNumber(treeNode.right) + 1;

}
``````

#### 2.计算二叉树的深度。

``````public static int getTreeDepth(TreeNode tree) {

if (tree == null) {
return 0;
}

int left = getTreeDepth(tree.left);
int right = getTreeDepth(tree.right);

return left >= right ? left + 1 : right + 1;
}

``````

#### 3.如何打印二叉树每层的节点。

``````public static void printByLevel(TreeNode tree) {
if (tree == null) {
return;
}

while (!queue.isEmpty()) {
TreeNode pop = queue.pop();
System.out.println(pop.val);
if (pop.left != null) {
}
if (pop.right != null) {
}
}

}
``````

#### 4.二叉树的Z型遍历。

`````` public static void printByZ(TreeNode tree) {

if (tree == null) {
return;
}

List<TreeNode> orderQueue = new ArrayList<>();
List<TreeNode> disorderQueue = new ArrayList<>();

while (!orderQueue.isEmpty()|| !disorderQueue.isEmpty()) {
if (!orderQueue.isEmpty()) {
for (int i = 0; i < orderQueue.size(); i++) {
TreeNode leaf = orderQueue.get(i);
if (leaf.left != null) {
}
if (leaf.right != null) {
}
}

for (TreeNode node : orderQueue) {
System.out.println(node.val);
}
orderQueue.clear();

}

if (!disorderQueue.isEmpty()) {

for (int i = 0; i < disorderQueue.size(); i++) {
TreeNode leaf = disorderQueue.get(i);
if (leaf.left != null) {
}
if (leaf.right != null) {
}
}

for (int i = disorderQueue.size()-1; i >=0 ; i--) {
TreeNode leaf = disorderQueue.get(i);
System.out.println(leaf.val);
}
disorderQueue.clear();
}
}

}
``````

#### 5.一个已经构建好的TreeSet，怎么完成倒排序。

``````public static void reverse(TreeNode tree) {

if (tree.left == null && tree.right == null) {
return;
}

TreeNode tmp = tree.right;

tree.right = tree.left;
tree.left = tmp;

reverse(tree.left);
reverse(tree.right);

}
``````

#### 6.二叉树的前序遍历。

``````public static void preOrderRecursion(TreeNode tree) {

if (tree != null) {
System.out.print(tree.val + "->");
preOrderRecursion(tree.left);
preOrderRecursion(tree.right);
}

}
``````

``````public static void preOrderNonRecursion(TreeNode tree) {

Stack<TreeNode> stack = new Stack<>();
TreeNode node = tree;
while (node != null || !stack.empty()) {
if (node != null) {
System.out.print(node.val + "->");
stack.push(node);
node = node.left;
} else {
TreeNode tem = stack.pop();
node = tem.right;
}
}
}
``````

#### 7.二叉树的中序遍历。

``````public static void middleOrderRecursion(TreeNode tree) {

if (tree != null) {
middleOrderRecursion(tree.left);
System.out.print(tree.val + "->");
middleOrderRecursion(tree.right);
}

}
``````

``````public static void middleOrderNonRecursion(TreeNode tree) {

Stack<TreeNode> stack = new Stack<>();
TreeNode node = tree;
while (node != null || !stack.isEmpty()) {
if (node != null) {
stack.push(node);
node = node.left;
} else {
TreeNode tem = stack.pop();
System.out.print(tem.val + "->");
node = tem.right;
}
}

}
``````

#### 8.二叉树的后序遍历。

``````public static void postOrderTraverseRecursion(TreeNode root) {
if (root != null) {
postOrderTraverseRecursion(root.left);
postOrderTraverseRecursion(root.right);
System.out.print(root.val + "->");
}
}
``````

``````public static void postOrderTraverseNonRecursion1(TreeNode root) {

if (root == null) {
return;
}

while (!stack.isEmpty()) {

TreeNode node = stack.pollLast();

if (node.left != null) {
}
if (node.right != null) {
}
}

for (TreeNode node : output) {
System.out.print(node.val + "->");
}

}
``````
##### 笔者个人总结，如有错误之处望不吝指出。

• 发表于 2020-05-04 12:08
• 阅读 ( 192 )
• 分类：网络文章

1. 小编 文章