二叉树的节点定义

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode():val(0),left(NULL),right(NULL){}
    TreeNode(int x):val(x),left(NULL),right(NULL){}
    TreeNode(int x,TreeNode* left,TreeNode* right):val(x),left(left),right(right){}
};

递归前序遍历

void preorder(TreeNode* root)
{
    if(!root)return;
    cout<<root->val<<' ';
    preorder(root->left);
    preorder(root->right);
}

非递归前序遍历

void preorder1(TreeNode* root)
{
    stack<TreeNode*>s;
    s.push(root);
    while(s.size())
    {
        auto t=s.top();
        s.pop();
        cout<<t->val<<' ';
        if(t->right)s.push(t->right);
        if(t->left)s.push(t->left);
    }
}

递归中序遍历

void inorder(TreeNode* root)
{
    if(!root)return;
    inorder(root->left);
    cout<<root->val<<' ';
    inorder(root->right);
}

非递归中序遍历

void inorder1(TreeNode* root)
{
    stack<TreeNode*>s;
    TreeNode* cur=root;
    while(s.size()||cur)
    {
        while(cur)
        {
            s.push(cur);
            cur=cur->left;
        }
        cur=s.top();
        cout<<cur->val<<' ';
        s.pop();
        cur=cur->right;
    }
}

递归后序遍历

void postorder(TreeNode* root)
{
    if(!root)return;
    postorder(root->left);
    postorder(root->right);
    cout<<root->val<<' ';
}

非递归后序遍历

void postorder1(TreeNode* root)
{
    stack<TreeNode*>s;
    TreeNode* cur=root;
    TreeNode* pre=NULL;
    while(s.size()||cur)
    {
        while(cur)
        {
            s.push(cur);
            cur=cur->left;
        }
        cur=s.top();
        if(!cur->right||cur->right==pre)
        {
            cout<<cur->val<<' ';
            s.pop();
            pre=cur;
            cur=NULL;
        }
        else
            cur=cur->right;
    }
}

层序遍历

void levelorder(TreeNode* root)
{
    queue<TreeNode*>q;
    q.push(root);
    while(q.size())
    {
        auto t=q.front();
        cout<<t->val<<' ';
        q.pop();
        if(t->left)q.push(t->left);
        if(t->right)q.push(t->right);
    }
}

二叉树自下而上 从右到左遍历

#include<bits/stdc++.h>
using namespace std;
struct TreeNode
{
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode():val(0),left(NULL),right(NULL){}
    TreeNode(char val):val(val),left(NULL),right(NULL){}
    TreeNode(char val,TreeNode*left,TreeNode* right):val(val),left(left),right(right){}
};
void invertLevelOrder(TreeNode* root)
{
    stack<TreeNode*>s;
    queue<TreeNode*>q;
    q.push(root);
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        s.push(t);
        if(t->left)q.push(t->left);
        if(t->right)q.push(t->right);
    }
    while(s.size())
    {
        cout<<s.top()->val<<' ';
        s.pop();
    }
}
int main()
{
    TreeNode *root = new TreeNode('A',
                                  new TreeNode('B',
                                               new TreeNode('D'),
                                               new TreeNode('E')),
                                  new TreeNode('C'));
    invertLevelOrder(root);
    return 0;
}

递归求树高

int GetHeight(TreeNode* root)
{
    if(!root)return 0;
    return max(GetHeight(root->left),GetHeight(root->right))+1;
}

非递归求树高 还可以求树的最大宽度和每层节点个数

int GetHeight1(TreeNode* root)
{
    queue<TreeNode*>q;
    q.push(root);
    int height=0;
    while(q.size())
    {
        int n=q.size();
        while(n--)
        {
            auto t=q.front();
            q.pop();
            if(t->left)q.push(t->left);
            if(t->right)q.push(t->right);
        }
        height++;
    }
    return height;
}

树的最大宽度

int width(TreeNode* root)
{
    queue<TreeNode*>q;
    q.push(root);
    int w=0;
    while(q.size())
    {
        int n=q.size();
        w=max(w,n);
        while(n--)
        {
            auto t=q.front();
            q.pop();
            if(t->left)q.push(t->left);
            if(t->right)q.push(t->right);
        }

    }
    return w;
}

每层节点个数

void levrl_num(TreeNode* root)
{
    queue<TreeNode*>q;
    q.push(root);
    int height=0;
    while(q.size())
    {
        int n=q.size();
        int num=n;
        while(n--)
        {
            auto t=q.front();
            q.pop();
            if(t->left)q.push(t->left);
            if(t->right)q.push(t->right);
        }
        height++;
        printf("第%d层的结点个数为:%d\n",height,num);
    }
}

二叉树按二叉链表形式存储，写一个判别给定二叉树是否是完全二叉树的算法

bool isCompleteTree(TreeNode* root)
{
    queue<TreeNode*>q;
    q.push(root);
    bool leaf=false;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        if(!t)
        {
            leaf=true;
            contiune;
        }
        if(leaf&&t)return false;
        if(t->left)q.push(t->left);
        if(t->right)q.push(t->right);
    }
    return true;
}

计算一棵给定二叉树的双分支节点数

法一

int DoubleNode(TreeNode* root)
{
    if(!root)return 0;
    if(root->left&&root->right)return DoubleNode(root->left)+DoubleNode(root->right)+1;
    else
        return DoubleNode(root->left)+DoubleNode(root->right);
}

法二

void dfs(TreeNode* root)
{
    if(!root)return;
    if(root->left&&root->right)res++;
    dfs(root->left);
    dfs(root->right);
}

设树B是一棵采用链式结构存储的二叉树，编写一个把树B中所有结点的左、右子树进行交换的函数

void SwapTree(TreeNode* root)
{
    if(!root)return;
    swap(root->left,root->right);
    SwapTree(root->left);
    SwapTree(root->right);
}

假设二叉树采用二叉链存储结构存储，设计一个算法，求先序遍历序列中第 k(1≤k≤二叉树中结点个数)个结点的值

void dfs(TreeNode* root)
{
    res++;//res为全局变量,初始值为0
    if(res==k)cout<<root->val;
    if(root->left)dfs(root->left);
    if(root->right)dfs(root->right);
}

已知二叉树以二叉链表存储，编写算法完成：对于树中每个元素值为x的结点，删去以它为根的子树

void dfs(TreeNode* &root,char x)
{
    if(!root)return;
    if(root->val==x)
    {
        root=NULL;
        return;
    }
    else
    {
        dfs(root->left);
        dfs(root->right);
    }
}

树中两个结点的最低公共结点

算法一 非递归

vector<TreeNode *> findPath(TreeNode *root, TreeNode *p)
{
    vector<TreeNode*>path;
    TreeNode* cur=root;
    TreeNode* pre=NULL;
    while(cur||path.size())
    {
        while(cur)
        {
            path.push_back(cur);
            cur=cur->left;
        }
        cur=path.back();
        if(cur->right&&cur->right!=pre)
            cur=cur->right;
        else
        {
            path.pop_back();
            if(cur==p)return path;
            pre=cur;
            cur=NULL;
        }
    }
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
    vector<TreeNode*>path1=findPath(root,p);
    vector<TreeNode*>path2=findPath(root,q);
    if(path1.size()>path2.size())
        swap(path1,path2);
    for(int i=0;i<path1.size();i++)
        if(path1[i]!=path2[i])
            return path1[i-1];
        return path1.back();
}

算法二 递归

TreeNode* lowestCommonAncestor2(TreeNode* root, TreeNode* p, TreeNode* q)
{
    if(!root)return NULL;
    if(root==p||root==q)
        return root;
    TreeNode* left=lowestCommonAncestor2(root->left,p,q);
    TreeNode* right=lowestCommonAncestor2(root->right,p,q);
    if(left&&right)
        return root;
    if(left==NULL)
        return right;
    else 
        return left;
}

在二叉树中有两个结点m和n,若m是n的祖先,则使用后序遍历可以找到从m到n的路径

递归

bool postorder(TreeNode* root, TreeNode* n) 
{
    // 边界情况：空结点 -> 查找失败
    if (!root) 
        return false;

    // 递归遍历左右子树
    if (root == n || postorder(root->left, n) || postorder(root->right, n)) 
    {
        // 如果当前结点是目标结点n，或者在左右子树中找到了目标结点
        // 输出当前结点的值，并返回true
        cout << root->val << ' ';
        return true;
    }
}

非递归

void postorder(TreeNode* root,TreeNode* n)
{
    TreeNode* cur=root;
    TreeNode* pre=NULL;
    stack<TreeNode*>s;
    while(s.size()||cur)
    {
        while(cur)
        {
            s.push(cur);
            cur=cur->left;
        }
        cur=s.top();
        if(!cur->right||cur->right==pre)
        {
            if(cur->val==n->val)
            {
                while(s.size())
                {
                    cout<<s.top()->val<<' ';
                    s.pop();
                }
                return;
            }
            s.top();
            pre=cur;
            cur=NULL;
        }
        else 
            cur=cur->right;
    }
}