树是一种特殊的数据结构，包括二叉树、平衡树、B树、红黑树等众多类型。其定义为
class BinaryTreeNode {
public int value;
public BinaryTreeNode leftNode;
public BinaryTreeNode rightNode;
public BinaryTreeNode(){
}
public BinaryTreeNode(int value){
this.value = value ;
this.leftNode = null;
this.rightNode = null;
}
}
二叉树中常见的算法题目均可以通过迭代的方式求出。其中最典型的就是树的构建和遍历。
相关代码见https://github.com/yuanfuqiang456/LeetCode/tree/master/src/Tree
（1）二叉树的先序遍历
1、递归解法
public static void printPreOrder1(BinaryTreeNode root) {
if (root == null) {
return;
} else {
System.out.print(root.value + " ");
}
if (root.leftNode != null) {
printPreOrder1(root.leftNode);
}
if (root.rightNode != null) {
printPreOrder1(root.rightNode);
}
}
2、非递归解法
利用栈
public static void printPreOrder2(BinaryTreeNode root) {
Stack<BinaryTreeNode> s = new Stack<BinaryTreeNode>();
BinaryTreeNode p = root;
while(p!=null||!s.empty())
{
while(p!=null)
{
System.out.println(p.value);
s.push(p);
p = p.leftNode;
}
if(!s.empty())
{
p= s.lastElement();
s.pop();
p=p.rightNode;
}
}
}
（2）二叉树的中序遍历
1、递归解法
public static void printInOrder1(BinaryTreeNode root) {
if (root != null) {
if (root.leftNode != null) {
printInOrder1(root.leftNode);
}
System.out.print(root.value + " ");
if (root.rightNode != null) {
printInOrder1(root.rightNode);
}
}
}
2、非递归解法
public static void printInOrder2(BinaryTreeNode root) {
Stack<BinaryTreeNode> s = new Stack<BinaryTreeNode>();
BinaryTreeNode p = root;
while(p!=null||!s.empty())
{
while(p!=null)
{
s.push(p);
p = p.leftNode;
}
if(!s.empty())
{
p= s.lastElement();
System.out.println(p.value);
s.pop();
p=p.rightNode;
}
}
}
（3）二叉树的后序遍历
1、递归解法
public static void printPostOrder1(BinaryTreeNode root) {
if (root != null) {
if (root.leftNode != null) {
printPostOrder1(root.leftNode);
}
if (root.rightNode != null) {
printPostOrder1(root.rightNode);
}
System.out.print(root.value + " ");
}
}
2、非递归解法
public static void printPostOrder2(BinaryTreeNode root) {
Stack<BinaryTreeNode> s = new Stack<BinaryTreeNode>();
BinaryTreeNode cur ;
BinaryTreeNode pre = null;
s.push(root);
while(!s.empty())
{
cur=s.lastElement();
if((cur.leftNode==null&&cur.rightNode==null)||
(pre!=null&&(pre==cur.leftNode||pre==cur.rightNode)))
{
System.out.println(cur.value); //如果当前结点没有孩子结点或者孩子节点都已被访问过
s.pop();
pre=cur;
}
else
{
if(cur.rightNode!=null)
s.push(cur.rightNode);
if(cur.leftNode!=null)
s.push(cur.leftNode);
}
}
}
（4）求二叉树的深度
算法思路：使用递归的思想，分左右子树最大深度来求出。类似先序遍历。
public static void MaxDeep(BinaryTreeNode root) {
if(root==null)
return 0;
int nleft = MaxDeep(root.leftNode);
int nright = MaxDeep(root.rightNode);
return nleft>nrigth?nleft+1：nright+1;
}
（5）根据前序遍历和中序遍历构建二叉树
算法思路：(在不含重复数字的前提下)根据先序遍历找到根节点，然后在中序遍历中将序列分为左子序列和右子序列。递归计算。
public static BinaryTreeNode Construct(int[] preOrder, int[] inOrder,int length){
if (preOrder == null || inOrder == null || length <= 0) {
return null;
}
try {
return ConstructCore(preOrder, 0, preOrder.length - 1, inOrder, 0,inOrder.length - 1);
} catch (InvalidPutException e) {
e.printStackTrace();
return null;
}
}
public static BinaryTreeNode ConstructCore(int[] preOrder,int startPreIndex, int endPreIndex,int[] inOrder,int startInIndex, int endInIndex) throws InvalidPutException {
int rootValue = preOrder[startPreIndex];
System.out.println("rootValue = " + rootValue);
BinaryTreeNode root = new BinaryTreeNode(rootValue);
// 只有一个元素
if (startPreIndex == endPreIndex) {
if (startInIndex == endInIndex
&& preOrder[startPreIndex] == inOrder[startInIndex]) {
System.out.println("only one element");
return root;
} else {
throw new InvalidPutException();
}
}
// 在中序遍历中找到根结点的索引
int rootInIndex = startInIndex;
while (rootInIndex <= endInIndex && inOrder[rootInIndex] != rootValue) {
++rootInIndex;
}
if (rootInIndex == endInIndex && inOrder[rootInIndex] != rootValue) {
throw new InvalidPutException();
}
int leftLength = rootInIndex - startInIndex;
int leftPreOrderEndIndex = startPreIndex + leftLength;
if (leftLength > 0) {
// 构建左子树
root.leftNode = ConstructCore(preOrder, startPreIndex + 1,
leftPreOrderEndIndex, inOrder, startInIndex,
rootInIndex - 1);
}
if (leftLength < endPreIndex - startPreIndex) {
// 右子树有元素,构建右子树
root.rightNode = ConstructCore(preOrder, leftPreOrderEndIndex + 1,endPreIndex, inOrder, rootInIndex + 1, endInIndex);
}
return root;
}
（6）序遍历二叉树的下一个节点
算法思路：若该节点有右子树，则写一个节点为右子树的最左节点；若该节点没有右子树，且还是其父节点的左子节点，下一个节点就是父节点；若该节点即没有右子树，还是其父节点的右子节点，则下个节点为一直向上遍历，直到找到一个节点A，这个节点是原始节点的“父辈”节点，且A是A的父节点的左子节点，A即为所求。（剑指offer8题）可画图看一看。
（7）树的子结构
算法思路：判断一棵树是不是另一棵树的子结构。采用递归方法。先判断根节点，再判断左子树，右子树。
（8）二叉树的镜像
算法思路：先序遍历二叉树，若遍历到的节点有子节点，则交换两个子节点。
（9）对称的二叉树
算法思路：如果前序遍历和对称的前序遍历一致，则二叉树对称。（若一个节点子树为空，需要把空打印出来，对称前序遍历是指向遍历右子树再遍历左子树）
（10）从上到下打印二叉树
算法思路：结合队列，打印某节点，将其左右节点入队列。若要按行打印，需要维护两个变量，分别表示当前没打印的节点数和下一层的节点数。
public static void PrintFromTop(BinaryTreeNode root)
{
if(root==null)
{
return;
}
Queue<BinaryTreeNode> queue = new LinkedList<BinaryTreeNode>();
queue.offer(root);
while(queue.size()!=0)
{
BinaryTreeNode node = queue.peek();
System.out.println(node.value);
queue.poll();
if(node.leftNode!=null)
{
queue.offer(node.leftNode);
}
if(node.rightNode!=null)
{
queue.offer(node.rightNode);
}
}
}
//按行打印出来
public static void PrintFromTop2(BinaryTreeNode root)
{
if(root==null)
{
return;
}
Queue<BinaryTreeNode> queue = new LinkedList<BinaryTreeNode>();
queue.offer(root);
int nextval = 0;
int nowval = 1;
while(queue.size()!=0)
{
BinaryTreeNode node = queue.peek();
System.out.print(node.value);
//queue.poll();
if(node.leftNode!=null)
{
queue.offer(node.leftNode);
nextval++;
}
if(node.rightNode!=null)
{
queue.offer(node.rightNode);
nextval++;
}
queue.poll();
--nowval;
if(nowval==0)
{
System.out.println();
nowval = nextval;
nextval = 0;
}
}
}
（11）判断一棵树是不是平衡二叉树
算法思路：后序遍历，分别判断左右子树是否平衡，并求得深度。是左右子树是平衡的时候，判断左右子树深度之差。
（12）求二叉查找树的第k大元素
算法思路：中序遍历
（13）求二叉树中节点的最大距离
算法思路：左子树到跟节点的距离+右子树到跟节点的最大距离
（14）最近公共祖先
算法思路：二叉搜索树，遍历，看当前点是否大于A小于B；不是二叉搜索树，将遍历路径放到队列（或者链表）中，找最后一个公共节点。
网友评论