创建二叉树
只有先序、后序、层序可以用来创建二叉树（且要添加虚空节点），中序是不可以的。
原因很简单，因为即使添加了虚空节点，中序序列仍然不可以唯一确定一棵二叉树。
树节点
struct t{
int value;
t *left,*right;
t(){
}
t(int v):value(v),left(NULL),right(NULL){
}
}
根据前序构建二叉树
//先序遍历数组s创建二叉树，size为数组大小，index为数组索引
//后序遍历创建二叉树可由index从大到小递减得到
t* createtree(int *s, int size, int &index) {
t *root = NULL;
if (index < size&&s[index] != 0) {
root = new t;
root->value = s[index];
cout << "building " << s[index] << endl;
root->left=createtree(s, size, ++index);
root->right=createtree(s, size, ++index);
return root;
}
else {
cout << "invaild" << endl;
return root;
}
}
根据后序构建二叉树
//先序遍历数组s创建二叉树，size为数组大小，index为数组索引
//后序遍历创建二叉树可由index从大到小递减得到
t* createtree(int *s, int size, int &index) {
t *root = NULL;
if (index < size&&s[index] != 0) {
root = new t;
root->value = s[index];
cout << "building " << s[index] << endl;
root->right=createtree(s, size, --index);
root->left=createtree(s, size, --index)
return root;
}
else {
cout << "invaild" << endl;
return root;
}
}
根据层次遍历构建二叉树
class Codec:
def serialize(self, root):
if not root: return "[]"
queue = collections.deque()
queue.append(root)
res = []
while queue:
node = queue.popleft()
if node:
res.append(str(node.val))
queue.append(node.left)
queue.append(node.right)
else: res.append("null")
return '[' + ','.join(res) + ']'
def deserialize(self, data):
if data == "[]": return
vals, i = data[1:-1].split(','), 1
root = TreeNode(int(vals[0]))
queue = collections.deque()
queue.append(root)
while queue:
node = queue.popleft()
if vals[i] != "null":
node.left = TreeNode(int(vals[i]))
queue.append(node.left)
i += 1
if vals[i] != "null":
node.right = TreeNode(int(vals[i]))
queue.append(node.right)
i += 1
return root
用三个指针分别指向数组第一项，第二项和第三项（如果存在的话），这里用 p1，p2，p3 来标记，分别表示当前处理的节点，当前处理的节点的左子节点和当前处理的节点的右子节点。
p1 每次移动一位，p2 和 p3 每次移动两位。
p1.left = p2; p1.right = p3。
持续上面的步骤直到 p1 移动到最后。
def deserialize(self, data):
if data == 'null': return None
nodes = data.split(',')
root = TreeNode(nodes[0])
q = collections.deque([root])
i = 0
while q and i < len(nodes) - 2:
cur = q.popleft()
lv = nodes[i + 1]
rv = nodes[i + 2]
i += 2
if lv != 'null':
l = TreeNode(lv)
q.append(l)
cur.left = l
if rv != 'null':
r = TreeNode(rv)
q.append(r)
cur.right = r
return root
以下只有完全二叉树才行。
//由层次遍历创建树
t* createtreebfs(int *s, int size, int index) {
t *root = NULL;
if (index < size&&s[index] != 0) {
root = new t;
root->value = s[index];
root->left = createtreebfs(s, size, 2 * index);
root->right = createtreebfs(s, size, 2 * index + 1);
}
return root;
}
查找x值
//查找x值
t* find(t* root, int x) {
if (root == NULL) {
return NULL;
}
if (root->value == x) {
return root;
}
else {
t* r = find(root->left,x);
if (r == NULL) {
return find(root->right, x);
}
else {
return r;
}
}
}
计算最大宽度
//计算宽度
//可以由levercount()中改造，int book[]数组存储每层节点个数
//也可以改造层次遍历
int calcuwidth(t *root) {
int lastwidth = 0, currwidth = 0;
int nwidth = 1;
queue<t*> q;
lastwidth = 1;
q.push(root);
while (!q.empty()) {
while (lastwidth != 0) {
t* r = q.front();
q.pop();
if (r->left != NULL)
q.push(r->left);
if (r->right != NULL)
q.push(r->right);
lastwidth--;
}
currwidth = q.size();
nwidth = nwidth > currwidth ? nwidth : currwidth;
lastwidth = currwidth;
}
return nwidth;
}
计算每一层宽度
int book[20];
void calcuWidth(node *root,int depth) {
if (root == NULL) {
return;
}
cout << root->value << " depth: " << depth << endl;
book[depth]++;
if (root->left) {
calcuWidth(root->left, depth+1);
}
if (root->right) {
calcuWidth(root->right, depth+1);
}
}
计算深度
// 计算深度
int calcudepth(t *root) {
if (root == NULL) {
return 0;
}
int ldepth = calcudepth(root->left);
int rdepth = calcudepth(root->right);
return ldepth > rdepth ? ldepth+1 : rdepth+1;
}
二叉树遍历
递归遍历
前序遍历
//前序遍历
void previsit(t *root) {
if (root != NULL) {
cout << root->value << endl;
previsit(root->left);
previsit(root->right);
}
else {
//cout << "invalid" << endl;
}
}
中序遍历
//中序遍历
void midvisit(t *root) {
if (root != NULL) {
midvisit(root->left);
cout << root->value << endl;
midvisit(root->right);
}
}
后序遍历
//后序遍历
void postvisit(t *root) {
if (root != NULL) {
postvisit(root->left);
postvisit(root->right);
cout << root->value << endl;
}
}
层次遍历
//层次遍历
void levelvisit(t *root) {
queue<t*> q;
q.push(root);
while (!q.empty()) {
t *node = q.front();
cout << node->value << endl;
q.pop();
if (node->left != NULL) {
q.push(node->left);
}
if (node->right != NULL) {
q.push(node->right);
}
}
}
非递归遍历算法
可以直接看这个Cyc2018
前序遍历
根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。因此其处理过程如下：
对于任一结点P：
1)访问结点P，并将结点P入栈;
2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P;
3)直到P为NULL并且栈为空，则遍历结束。
void preOrder2(BinTree *root) //非递归前序遍历
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<<p->data<<" ";
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
还有另外一种实现方法，类似层次遍历，不过换成stack，要注意先放右孩子，保证左孩子在右孩子前输出。推荐记忆这个
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) continue;
ret.add(node.val);
stack.push(node.right); // 先右后左，保证左子树先遍历
stack.push(node.left);
}
return ret;
}
中序遍历
根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：
对于任一结点P，
1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
3)直到P为NULL并且栈为空则遍历结束。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if (root == null) return ret;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
ret.add(node.val);
cur = node.right;
}
return ret;
}
后续遍历
后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。下面介绍两种思路。
第一种思路：对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问， 因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就 保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是 否是第一次出现在栈顶。
void postOrder2(BinTree *root) //非递归后序遍历
{
stack<BTNode*> s;
BinTree *p=root;
BTNode *temp;
while(p!=NULL||!s.empty())
{
while(p!=NULL) //沿左子树一直往下搜索，直至出现没有左子树的结点
{
BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
btn->btnode=p;
btn->isFirst=true;
s.push(btn);
p=p->lchild;
}
if(!s.empty())
{
temp=s.top();
s.pop();
if(temp->isFirst==true) //表示是第一次出现在栈顶
{
temp->isFirst=false;
s.push(temp);
p=temp->btnode->rchild;
}
else //第二次出现在栈顶
{
cout<<temp->btnode->data<<" ";
p=NULL;
}
}
}
}
第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存 在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了 每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
void postOrder3(BinTree *root) //非递归后序遍历
{
stack<BinTree*> s;
BinTree *cur; //当前结点
BinTree *pre=NULL; //前一次访问的结点
s.push(root);
while(!s.empty())
{
cur=s.top();
if((cur->lchild==NULL&&cur->rchild==NULL)||
(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
{
cout<<cur->data<<" "; //如果当前结点没有孩子结点或者孩子节点都已被访问过
s.pop();
pre=cur;
}
else
{
if(cur->rchild!=NULL)
s.push(cur->rchild);
if(cur->lchild!=NULL)
s.push(cur->lchild);
}
}
}
第三种思路，推荐记忆这个
前序遍历为 root -> left -> right，后序遍历为 left -> right -> root。可以修改前序遍历成为 root -> right -> left，那么这个顺序就和后序遍历正好相反。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) continue;
ret.add(node.val);
stack.push(node.left);
stack.push(node.right);
}
Collections.reverse(ret);
return ret;
}
求叶子节点个数
//计算叶子个数
int calculeaf(t *root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
else {
return calculeaf(root->left) + calculeaf(root->right);
}
}
求第k层（深度）的节点个数
//求第k层（深度）的节点个数
//求k层个数即求k-1层孩子个数，第一层就一个节点，就是1
int levelcount(t* root, int k){
if (root == NULL || k < 0) {
return 0;
}
if (k == 1) {
return 1;
}
int l = levelcount(root->left, k - 1);
int r = levelcount(root->right, k - 1);
return l + r;
}
二叉树java实现
节点
static class Tree{
Tree left,right;
int data;
Tree(int data){
this.data=data;
}
}
遍历
static void visitLVR(Tree root){
if(root!=null){
visitLVR(root.left);
System.out.print(root.data+" ");
visitLVR(root.right);
}
}
static void visitVLR(Tree root){
if(root!=null){
System.out.print(root.data+" ");
visitVLR(root.left);
visitVLR(root.right);
}
}
static void visitLRV(Tree root){
if(root!=null){
visitLRV(root.left);
visitLRV(root.right);
System.out.print(root.data+" ");
}
}
static void visitlevel(Tree root){
ArrayDeque<Tree> arrayDeque=new ArrayDeque<>();
arrayDeque.add(root);
int last=1;
while (arrayDeque.size()>0){
Tree t=arrayDeque.pollFirst();
System.out.print(t.data+" ");
if(t.left!=null)
arrayDeque.add(t.left);
if(t.right!=null)
arrayDeque.add(t.right);
}
}
创建二叉树
static void visitLVR(Tree root){
if(root!=null){
visitLVR(root.left);
System.out.print(root.data+" ");
visitLVR(root.right);
}
}
static void visitVLR(Tree root){
if(root!=null){
System.out.print(root.data+" ");
visitVLR(root.left);
visitVLR(root.right);
}
}
static void visitLRV(Tree root){
if(root!=null){
visitLRV(root.left);
visitLRV(root.right);
System.out.print(root.data+" ");
}
}
static int index=0;
/**
* 先序创建二叉树
* @param data
* @return
*/
static Tree createTree1(int[] data){
Tree root=null;
if(index>=0&&index<data.length&&data[index]!='*'){
root=new Tree(data[index]);
index++;
root.left=createTree1(data);
index++;
root.right=createTree1(data);
}
return root;
}
/**
* 按后序创建二叉树
* @param data
* @return
*/
static Tree createTree2(int[] data){
Tree root=null;
if(index>=0&&data[index]!='*'){
root=new Tree(data[index]);
index--;
root.left=createTree2(data);
index--;
root.right=createTree2(data);
}
return root;
}
/**
* 按层次遍历，记住起始不能是0了，2*0=0，所以要加1个，1开始
* @param data
* @param index1
* @return
*/
static Tree createTree3(int[] data,int index1){
Tree root=null;
if(index1<data.length&&data[index1]!='*'){
root=new Tree(data[index1]);
root.left=createTree3(data,2*index1);
root.right=createTree3(data,2*index1+1);
}
return root;
}
public static void main(String[] args){
int[] data=new int[]{1,2,'*',3,'*','*',4,'*','*'};
data=new int[]{'*','*','*',3,2,'*','*',4,1};
data=new int[]{'*',1,2,4,'*',3,'*','*','*','*'};
Tree root=createTree3(data,1);
visitLRV(root);
System.out.println();
visitVLR(root);
System.out.println();
}
计算深度
/**
* 计算深度
* @param root
* @return
*/
static int depth(Tree root){
if(root==null)
return 0;
int left=depth(root.left);
int right=depth(root.right);
return max(left,right)+1;
}
计算宽度
/**
* 计算宽度
* @param root
* @return
*/
static int width(Tree root){
if(root==null)
return 0;
ArrayDeque<Tree> arrayDeque=new ArrayDeque<>();
arrayDeque.add(root);
int last=1;
int maxWidth=1;
while(!arrayDeque.isEmpty()){
while(last-->0){
Tree t=arrayDeque.pollFirst();
if(t.left!=null){
arrayDeque.add(t.left);
}
if(t.right!=null){
arrayDeque.add(t.right);
}
}
last=arrayDeque.size();
maxWidth=max(maxWidth,last);
}
return maxWidth;
}
查找x值
/**
* 二叉树查找x值
* @param root
* @param key
* @return
*/
static Tree find(Tree root,int key){
if(root==null){
return null;
}
if(root.data==key){
return root;
}else{
Tree t=find(root.left,key);
if(t!=null){
return t;
}else{
return find(root.right,key);
}
}
}
后序遍历非递归
/**
* 后序遍历非递归实现
* @param root
*/
static void postOrder(Tree root){
ArrayDeque<Tree> arrayDeque=new ArrayDeque<>();
arrayDeque.push(root);
Tree pre=null;
Tree cur=null;
while(!arrayDeque.isEmpty()){
cur=arrayDeque.peekFirst();
if((cur.left==null&&cur.right==null)
||(pre!=null&&(pre==cur.left||pre==cur.right))){
System.out.print(cur.data+" ");
arrayDeque.pop();
pre=cur;
}else{
if(cur.right!=null){
arrayDeque.push(cur.right);
}
if(cur.left!=null){
arrayDeque.push(cur.left);
}
}
}
}
前序中序得到后序
后续遍历
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
string res;
void postOrder(string preorder, string midorder, int sp, int se, int ms, int me){
if(sp > se || ms > me) return;
res = preorder[sp] + res; //其实是给倒序了，正常后序遍历应该是lrv, 因此这里是vrl然后又给倒序了
int mid = ms;
for(mid = ms; mid <= me; mid++){
if(midorder[mid] == preorder[sp]) break;
}
postOrder(preorder, midorder, mid-ms+sp+1, se, mid+1, me);//这里是先右孩子
postOrder(preorder, midorder, sp+1, mid-ms+sp, ms, mid-1); //然后左孩子
}
int main(){
string str1, str2;
while(cin>>str1>>str2){
postOrder(str1, str2, 0, (int)str1.length()-1, 0, (int)str2.length()-1);
cout<<res<<endl;
res = "";
}
return 0;
}
前序中序重构二叉树
struct TreeNode{
int val;
TreeNode * left, *right;
TreeNode(int x): val(x), left(NULL), right(NULL){}
};
TreeNode* constTree(string preorder, string midorder, int sp, int se, int ms, int me){
if (sp > se || ms > me) {
return NULL;
}
TreeNode * node = new TreeNode(preorder[sp]);
int mid = ms;
for(mid = ms; mid <= me; mid++){
if(midorder[mid] == preorder[sp]) break;
}
node->left = constTree(preorder, midorder, sp+1, mid-ms+sp, ms, mid-1);
node->right = constTree(preorder, midorder, mid-ms+sp+1, se, mid+1, me);
return node;
}
找最近公共祖先
方法1： 遍历，时间复杂度o(N)
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left if left else right
方法2： 存储父节点o(N), 父节点遍历o(log(N))
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
parent = {}
def dfs(r):
nonlocal parent
if r.left:
parent[r.left] = r
dfs(r.left)
if r.right:
parent[r.right] = r
dfs(r.right)
dfs(root) # o(N)
p_path = [p]
while p in parent:
p = parent[p]
p_path.append(p)
q_path = [q]
while q in parent:
q = parent[q]
q_path.append(q)
p_path = p_path[::-1]
q_path = q_path[::-1]
# print(p_path)
# print(q_path)
r = None
for i in range(min(len(p_path), len(q_path))):
if p_path[i] == q_path[i]:
r = p_path[i]
return r
方法3， 倍增法，参考
时间复杂度：预处理 O(nlogn，回答每个询问 O(logn) 空间复杂度：预处理需要 O(nlogn)的空间。