二叉树算法系列文章

算法知识梳理(11) - 二叉树相关算法第一部分
算法知识梳理(12) - 二叉树相关算法第二部分
算法知识梳理(13) - 二叉树相关算法第三部分

一、概述

二叉树算法第二部分内容包括以下几个主题：

获得二叉树的镜像
判断元素是否存在于二叉树中
打印二叉树中和为s的路径
获得二叉树的最大距离
判断二叉树是否是平衡树

二、代码实现

2.1 获得二叉树的镜像

代码实现

public class Untitled {static class Tree {int size;Node root;}static class Node {Node parent;Node left;Node right;int value;}static void insertNode(Tree tree, int value) {if (tree == null) {return;}Node tNode = tree.root;//待插入结点的父结点，如果遍历完为空，说明此时是一个空树。Node pNode = null;//新的结点。Node nNode = new Node();nNode.value = value;while (tNode != null) {pNode = tNode;if (tNode.value > value) {tNode = tNode.left;} else {tNode = tNode.right;}}nNode.parent = pNode;if (pNode == null) {tree.root = nNode;} else if (pNode.value > value) {pNode.left = nNode;} else {pNode.right = nNode;}tree.size++;}static Tree createBinTree(int p[], int len) {Tree tree = new Tree();for (int i = 0; i < len; i++) {int value = p[i];insertNode(tree, value);}return tree;}static void swapTree(Node node) {if (node == null) {return;}Node temp = node.left;node.left = node.right;node.right = temp;swapTree(node.left);swapTree(node.right);}static void printInOrder(Node node) {if (node == null) {return;}printInOrder(node.left);//遍历完左子树后，打印根结点，最后遍历右子树。System.out.println(node.value);printInOrder(node.right);}public static void main(String[] args) {int p[] = {3, 5, 6, 1, 2, 4, -1, -3};Tree tree = createBinTree(p, p.length);System.out.println("- 转换前 -");printInOrder(tree.root);swapTree(tree.root);System.out.println("- 转换后 -");printInOrder(tree.root);}
}
复制代码

运行结果

- 转换前 -
-3
-1
1
2
3
4
5
6
- 转换后 -
6
5
4
3
2
1
-1
-3
复制代码

2.2 判断元素是否存在于二叉树中

代码实现

public class Untitled {static class Tree {int size;Node root;}static class Node {Node parent;Node left;Node right;int value;}static void insertNode(Tree tree, int value) {if (tree == null) {return;}Node tNode = tree.root;//待插入结点的父结点，如果遍历完为空，说明此时是一个空树。Node pNode = null;//新的结点。Node nNode = new Node();nNode.value = value;while (tNode != null) {pNode = tNode;if (tNode.value > value) {tNode = tNode.left;} else {tNode = tNode.right;}}nNode.parent = pNode;if (pNode == null) {tree.root = nNode;} else if (pNode.value > value) {pNode.left = nNode;} else {pNode.right = nNode;}tree.size++;}static Tree createBinTree(int p[], int len) {Tree tree = new Tree();for (int i = 0; i < len; i++) {int value = p[i];insertNode(tree, value);}return tree;}static boolean isKInTree(Node node, int k) {if (node == null) {return false;}if (node.value == k) {return true;}boolean has;//先在左子树中寻找，如果左子树中找到了，那么就不需要在右子树中寻找了。has = isKInTree(node.left, k);if (!has) {has = isKInTree(node.right, k);}return has;}public static void main(String[] args) {int p[] = {3, 5, 6, 1, 2, 4, -1, -3};Tree tree = createBinTree(p, p.length);System.out.println("5 is in tree=" + isKInTree(tree.root, 5));System.out.println("9 is in tree=" + isKInTree(tree.root, 9));}
}
复制代码

运行结果

>> 5 is in tree=true
>> 9 is in tree=false
复制代码

2.3 打印二叉树中和为 s 的路径

问题描述

输入一个整数和一棵二叉树，打印出和与输入整数相等的所有路径，从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。

代码实现

import java.util.LinkedList;public class Untitled {static class Tree {int size;Node root;}static class Node {Node parent;Node left;Node right;int value;}static void insertNode(Tree tree, int value) {if (tree == null) {return;}Node tNode = tree.root;//待插入结点的父结点，如果遍历完为空，说明此时是一个空树。Node pNode = null;//新的结点。Node nNode = new Node();nNode.value = value;while (tNode != null) {pNode = tNode;if (tNode.value > value) {tNode = tNode.left;} else {tNode = tNode.right;}}nNode.parent = pNode;if (pNode == null) {tree.root = nNode;} else if (pNode.value > value) {pNode.left = nNode;} else {pNode.right = nNode;}tree.size++;}static Tree createBinTree(int p[], int len) {Tree tree = new Tree();for (int i = 0; i < len; i++) {int value = p[i];insertNode(tree, value);}return tree;}static void printSum(LinkedList<Node> curPath, Node curNode, int curSum, int expectSum) {if (curNode == null) {return;}curPath.offer(curNode);boolean isLeaf = curNode.left == null && curNode.right == null;int sum = curSum + curNode.value;//如果是叶结点，并且和满足要求，那么打印出所有的路径。if (isLeaf && sum == expectSum) {for (int i = 0; i < curPath.size(); i++) {System.out.println(String.valueOf(curPath.get(i).value));}} else {printSum(curPath, curNode.left, sum, expectSum);printSum(curPath, curNode.right, sum, expectSum);}//当其左右子树都遍历完之后，将当前结点出栈。curPath.pop();}public static void main(String[] args) {int p[] = {3, 5, 6, 1, 2, 4, -1, -3};Tree tree = createBinTree(p, p.length);printSum(new LinkedList<Node>(), tree.root, 0, 12);}
}
复制代码

运行结果

2
5
4
复制代码

2.4 获得二叉树的最大距离

问题描述

二叉树距离 指的是两个 叶结点之间边的个数，计算一个二叉树的最大距离有两种情况，最终的目的就是要获得这两种情况的值，并取其最大值作为该结点的最大距离：

路径经过左子树的最深结点，通过根结点，再到右子树的最深结点，在这种情况下，最大距离等于左子树的高度加上右子树的高度在加上2。
路径不穿过根结点，而是左子树或右子树的最大距离路径，在这种情况下，最大距离等于这两者的最大值。

对于每个结点，定义两个额外的属性，maxDistance表示 以该结点为根结点的子树的最大距离，而maxDepth为 以该结点为根结点的子树到最深结点的距离，对于每个叶结点来说，这两个值为0，而对于每个非叶结点来说，这两个值是通过它的左右孩子结点的这两个属性计算出来的。

代码实现

public class Untitled {static class Tree {int size;Node root;}static class Node {Node parent;Node left;Node right;int value;int maxDistance;int maxDepth;}static void insertNode(Tree tree, int value) {if (tree == null) {return;}Node tNode = tree.root;//待插入结点的父结点，如果遍历完为空，说明此时是一个空树。Node pNode = null;//新的结点。Node nNode = new Node();nNode.value = value;while (tNode != null) {pNode = tNode;if (tNode.value > value) {tNode = tNode.left;} else {tNode = tNode.right;}}nNode.parent = pNode;if (pNode == null) {tree.root = nNode;} else if (pNode.value > value) {pNode.left = nNode;} else {pNode.right = nNode;}tree.size++;}static Tree createBinTree(int p[], int len) {Tree tree = new Tree();for (int i = 0; i < len; i++) {int value = p[i];insertNode(tree, value);}return tree;}static void calculateMaxTreeDistance(Node node) {//如果是空结点，那么不需要计算。if (node == null) {return;}if (node.left == null && node.right == null) {return;}int leftDistance = 0;int leftDepth = -1;if (node.left != null) {calculateMaxTreeDistance(node.left);leftDistance = node.left.maxDistance;leftDepth = node.left.maxDepth;}int rightDistance = 0;int rightDepth = -1;if (node.right != null) {calculateMaxTreeDistance(node.right);rightDistance = node.left.maxDistance;rightDepth = node.left.maxDepth;}//深度为左右孩子结点的深度最大值+1node.maxDepth = leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;//(1) 通过根结点，则选取左子树的深度+右子树深度+2int throughRoot = leftDepth + rightDepth + 2;//(2) 不通过根结点，则选取左右子树的距离最大值。int notThroughRoot = leftDistance > rightDistance ? leftDistance : rightDistance;//取以上两者的最大值，作为该结点的最大距离属性。node.maxDistance = throughRoot > notThroughRoot ? throughRoot : notThroughRoot;}static void printInOrder(Node node) {if (node == null) {return;}printInOrder(node.left);//遍历完左子树后，打印根结点，最后遍历右子树。System.out.println("value=" + node.value + ", depth=" + node.maxDepth + ", distance=" + node.maxDistance);printInOrder(node.right);}public static void main(String[] args) {int p[] = {3, 5, 6, 1, 2, 4, -1, -3};Tree tree = createBinTree(p, p.length);calculateMaxTreeDistance(tree.root);System.out.println("最大距离=" + tree.root.maxDistance);}
}
复制代码

运行结果

>> 最大距离=6
复制代码

2.5 判断二叉树是否是平衡树

问题描述

平衡二叉树 具有以下性质：它是一棵空树或它的 左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

解决思路

根据平衡二叉树的定义，对于每个结点需要满足两个条件：

左右子树都是平衡树
左右子树的高度差小于等于1

因此，我们可以采用递归的方式来实现，对于每个结点，返回一个数据结构BalanceValue表示以该结点为根结点的子树是否是平衡树，以及它的高度（叶结点的高度为0）。

代码实现

public class Untitled {static class Tree {int size;Node root;}static class Node {Node parent;Node left;Node right;int value;}static class BalanceValue {boolean isBalance;int treeHeight;}static void insertNode(Tree tree, int value) {if (tree == null) {return;}Node tNode = tree.root;//待插入结点的父结点，如果遍历完为空，说明此时是一个空树。Node pNode = null;//新的结点。Node nNode = new Node();nNode.value = value;while (tNode != null) {pNode = tNode;if (tNode.value > value) {tNode = tNode.left;} else {tNode = tNode.right;}}nNode.parent = pNode;if (pNode == null) {tree.root = nNode;} else if (pNode.value > value) {pNode.left = nNode;} else {pNode.right = nNode;}tree.size++;}static Tree createBinTree(int p[], int len) {Tree tree = new Tree();for (int i = 0; i < len; i++) {int value = p[i];insertNode(tree, value);}return tree;}static BalanceValue isTreeBalance(Node node) {BalanceValue value = new BalanceValue();if (node == null) {value.treeHeight = -1;value.isBalance = true;return value;}//先确定左子树是否是平衡树。BalanceValue left = isTreeBalance(node.left);if (left.isBalance) {//再确定右子树是否是平衡树。BalanceValue right = isTreeBalance(node.right);if (right.isBalance) {int leftHeight = left.treeHeight;int rightHeight = right.treeHeight;//左右的高度差是否小于等于1。if (Math.abs(leftHeight - rightHeight) <= 1) {//得到当前结点的高度。value.treeHeight = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;value.isBalance = true;return value;}}}value.isBalance = false;return value;}public static void main(String[] args) {int p[] = {3, 5, 6, 1, 2, 4, -1, -3, -99, -100};Tree tree = createBinTree(p, p.length);System.out.println("平衡树=" + isTreeBalance(tree.root).isBalance);}
}
复制代码