二叉树

近况

最近实在太忙了，上周末还加了两天班，这两天利用晚上下班时间(并不是正常下班, 你懂的)，把二叉树相关的算法大概敲了一遍，找找感觉。

代码

直接上代码：

#ifndef __TREE_H__
#define __TREE_H__
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <limits.h>

using namespace std;

// Definition for a binary tree node.
class TreeNode
{
public:
  TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}

public:
  int value;
  TreeNode *left;
  TreeNode *right;
};

class Solution
{
public:
  using link_type = TreeNode *;

  // create
  void CreateTree(link_type& T)
  {
    int i;
    cin >> i;

    if (i == 0)
    {
      T = nullptr;
    }
    else
    {
      T = new TreeNode(i);
      CreateTree(T->left);
      CreateTree(T->right);
    }
  }
	
	// Destory Tree
  void DestoryTree(link_type T){
	if(T == nullptr){
	 return ;
	}

	DestoryTree(T->left);
	DestoryTree(T->right);

	delete T;
	T = nullptr;
  }

  // 非递归前序遍历
  void preTraverseNoRec(link_type T){
	if(T == nullptr){
		return ;
	}

	stack<link_type> stack;
	link_type curr = T;

	while(curr || !stack.empty()){
		while(curr){
			cout << " " << curr->value; // 输出
			stack.push(curr);
			curr = curr->left;
		}

		curr = stack.top();
		stack.pop();
		curr = curr->right;
	}
  }

  // 前序遍历
  void preTraverse(link_type T)
  {
    if (T == nullptr)
    {
      return;
    }

    cout << " " << T->value;
    preTraverse(T->left);
    preTraverse(T->right);
  }

  // 非递归中序遍历 
  void midTraverseNoRec(link_type T){
	if(T == nullptr){
		return;		
	}

	stack<link_type> stack; // 使用栈保存
	link_type curr = T; // 当前节点 

	while(curr || !stack.empty()){
		// 先遍历左子树入栈	
		while(curr){                  
			stack.push(curr);
			curr = curr->left;
		}

		curr = stack.top();
		stack.pop();

		cout <<" " <<  curr->value;
		curr = curr->right; // 使右节点变为左节点
	}
 }

  // 中序遍历
  void midTraverse(link_type T)
  {
    if (T == nullptr)
    {
      return;
    }

    midTraverse(T->left);
    cout << " " << T->value;
    midTraverse(T->right);
  }
 
  // 非递归后续遍历
  void postTraverseNoRec(link_type T){
	if(T == nullptr){
		return;
	}

	stack<link_type> stack;
	link_type curr = T; 
	link_type last = nullptr; // 保存右节点标志

	while(curr || !stack.empty()){
		while(curr){
			stack.push(curr);
			curr = curr->left;
		}

		curr = stack.top();
		if(curr->right == nullptr || curr->right == last){
			cout << " " << curr->value; // 打印元素
			stack.pop();
			
			// 记录上一个访问节点
			// 用于判断"访问根节点前，右子树是否访问过"
			last = curr;
			curr = nullptr;
		}
		else{
			curr = curr->right; // 右节点当做左节点处理
		}
	}
  }

  // 后续遍历
  void postTraverse(link_type T)
  {
    if (T == nullptr)
    {
      return;
    }

    postTraverse(T->left);
    postTraverse(T->right);
    cout << " " << T->value;
  }

  // 层次遍历
  void levelTraverse(link_type T){
  	if(T == nullptr){
		return ;
	}

	queue<link_type> queue;
	queue.push(T);
	link_type curr = nullptr;

	while(!queue.empty()){
		curr = queue.front();
		queue.pop();
		// 输出
		cout << " " << curr->value;
		
		if(curr->left != nullptr){
			queue.push(curr->left);		
		}

		if(curr->right != nullptr){
			queue.push(curr->right);
		}
	}
  }

  // 树的深度
  int BinaryTreeDepth(link_type T)
  {
	if(T == nullptr)
	{
		return 0;  
	}

	return (max(BinaryTreeDepth(T->left), BinaryTreeDepth(T->right)) + 1);
  }
  
  // 比较两个树是否相等
  bool CompareTwoBinaryTree(link_type TA, link_type TB)
  {
	// 均为空
	if(TA == nullptr && TB == nullptr)
	{
		return true;
	}
	else if(TA == nullptr || TB == nullptr) 
	{
		return false;
	}
	
	// 比较data
	if(TA->value != TB->value)
	{
		return false;
	}

	return CompareTwoBinaryTree(TA->left, TB->left) && CompareTwoBinaryTree(TA->right, TB->right);
  }

  // 二叉树节点个数
  int BinaryTreeNodeNumbers(link_type T){
		if(T == nullptr){
			return 0;
		}		  
		
		return BinaryTreeNodeNumbers(T->left) + BinaryTreeNodeNumbers(T->right) + 1;
  }
 
 // 求二叉树第 K 层节点的个数
 int BinaryTreeKLevelSize(link_type T, int k){
 	if(T == nullptr || k < 0){
		return 0; 
	}

	// 第 0 层
	if(k == 0){  
		return 1;
	}

	return BinaryTreeKLevelSize(T->left, k - 1) + BinaryTreeKLevelSize(T->right, k - 1);
 }
 
 // 判断二叉树是否为平衡二叉树
 bool isAVLTree(link_type T){
	if(T == nullptr){
		return true;
	}

	if(abs(BinaryTreeDepth(T->left) - BinaryTreeDepth(T->right)) > 1){
		return false;	
	}
	
	return isAVLTree(T->left) && isAVLTree(T->right);
 }

 // 判断是否为二分查找树 BST
 bool isValidBST(link_type T){
 	return isValidBST(T, INT_MIN, INT_MAX);
 }

 bool isValidBST(link_type T, int minVal, int maxVal){
 	if(T == nullptr){
		return true;
	}

	if(T->value < minVal || T->value > maxVal){
		return false;
	}

	return isValidBST(T->left, minVal, T->value) && isValidBST(T->right, T->value, maxVal);
 }

 // 非递归断是否为二分查找树 BST (中序非递归)
 bool isValidBSTNoRec(link_type T){
	if(T == nullptr){
		return true;
	}

	stack<link_type> stack; // 栈
	link_type curr = T; // 当前节点
	link_type pre = nullptr; // 记录前一个节点

	while(curr || !stack.empty()){
		while(curr){
			stack.push(curr);
			curr = curr->left;
		}

		curr = stack.top();
		stack.pop();
		
		if(pre && pre->value > curr->value){
			return false;
		} 

		pre = curr;
		curr = curr->right;	
	}

	return true;
 }

 // 求二叉树的镜像
 link_type mirrorTree(link_type T){
	if(T == nullptr){
		return T;
	}
	
	link_type newRoot = new TreeNode(T->value);

	newRoot->left = mirrorTree(T->right);
	newRoot->right = mirrorTree(T->left);

	return newRoot;
 }

 // 判断两棵树是否互为镜像
 bool isMirrorTree(link_type TA, link_type TB){
 	if(TA == nullptr && TB == nullptr){
		return true;
	}
	else if(TA == nullptr || TA == nullptr){
		return false;
	}

	if(TA->value != TB->value){
		return false;
	}

	return isMirrorTree(TA->left, TB->right) && isMirrorTree(TA->right, TB->left);
 }

 // 树中两个节点的最低公共祖先节点
 link_type getLastCommonParentNode(link_type root, link_type TA, link_type TB){
 	if(root == nullptr){
		return nullptr;
	}

	if(root == TA || root == TB){
		return root;
	}

	link_type commonleft = getLastCommonParentNode(root->left, TA, TB);
	link_type commonright = getLastCommonParentNode(root->right, TA, TB);

	if(commonleft != nullptr && commonright != nullptr){
		return root;
	}

	if(commonleft != nullptr){
		return commonleft;
	}

	return commonright;
 }
 
};

#endif // !__TREE_H__

测试代码：

#include <iostream>
#include <bitset>
#include <unordered_map>
#include <vector>
#include "tree.h"

using namespace std;

int main()
{
	// binary  tree
	TreeNode* root;
	Solution solution;

	cout << "create tree begin!" << endl;
	solution.CreateTree(root); 	// create
	cout << endl;
	cout << "create tree end!" << endl;

	cout << "preTraverse tree begin!" << endl;
	solution.preTraverse(root); // 前序
	cout << endl;
	
	cout << "no recursive preTraverse tree begin!" << endl;
	solution.preTraverseNoRec(root); // 非递归前序
	cout << endl;

	cout << "midTraverse tree begin!" << endl;
	solution.midTraverse(root); // 中序
	cout << endl;
	
	cout << "no recursive midTraverse tree begin!" << endl;
	solution.midTraverseNoRec(root); // 非递归中序
	cout << endl;

	cout << "postTraverse tree begin!" << endl;
	solution.postTraverse(root); // 后序
	cout << endl;
	
	cout << "no recursive postTraverse tree begin!" << endl;
	solution.postTraverseNoRec(root); // 非递归后序
	cout << endl;
	
	cout << "levelTraverse tree begin!" << endl;
	solution.levelTraverse(root); // 层次
	cout << endl;

	cout << "binary tree node numbers: "<< solution.BinaryTreeNodeNumbers(root) << endl;
	
	cout << "binary tree depth: "<< solution.BinaryTreeDepth(root) << endl;
	
	// 输出二叉树 1.2 层节点个数
	cout << "binary tree 1 level size: " << solution.BinaryTreeKLevelSize(root, 1)  << endl; 
  	cout << "binary tree 2 level size: " << solution.BinaryTreeKLevelSize(root, 2)  << endl;

	cout << "binary tree is valid BST: " << solution.isValidBST(root) << endl;
	cout << "binary tree is valid BST no rec: " << solution.isValidBSTNoRec(root) << endl;

	cout << "binary tree is valid AVL: " << solution.isAVLTree(root) << endl;

	cout << "binary tree test end！" << endl;
	solution.DestoryTree(root);
	return 0;
}

以前序遍历 1->2->3->2->4->5 为例，过一遍用例，打印结果如下：

[root@yejy binaryTree]# valgrind ./a.out 
==18094== Memcheck, a memory error detector
==18094== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==18094== Using Valgrind-3.14.0 and LibVEX; rerun with -h for copyright info
==18094== Command: ./a.out
==18094== 
create tree begin!
1
2
3
0
0
2
0
0
4
5
0
0
0

create tree end!
preTraverse tree begin!
 1 2 3 2 4 5
no recursive preTraverse tree begin!
 1 2 3 2 4 5
midTraverse tree begin!
 3 2 2 1 5 4
no recursive midTraverse tree begin!
 3 2 2 1 5 4
postTraverse tree begin!
 3 2 2 5 4 1
no recursive postTraverse tree begin!
 3 2 2 5 4 1
levelTraverse tree begin!
 1 2 4 3 2 5
binary tree node numbers: 6
binary tree depth: 3
binary tree 1 level size: 2
binary tree 2 level size: 3
binary tree is valid BST: 0
binary tree is valid BST no rec: 0
binary tree is valid AVL: 1
binary tree test end！
==18094== 
==18094== HEAP SUMMARY:
==18094==     in use at exit: 0 bytes in 0 blocks
==18094==   total heap usage: 26 allocs, 26 frees, 5,904 bytes allocated
==18094== 
==18094== All heap blocks were freed -- no leaks are possible
==18094== 
==18094== For counts of detected and suppressed errors, rerun with: -v
==18094== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

大概就这样，晚安！！