二叉树常用操作

1，前序遍历

2，中序遍历

3，后序遍历

4，层序遍历

5，二叉树的节点总数 compare 叶子节点数

（C++实现）

一，前序遍历（非递归）LeetCode144

void preOrder1(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;
        }
    }
}
/*while (!s.empty() || p)
{
    if (p)
    {
        cout << p->data;
        s.push(p);
        p = p->lchild;
    }
    else
    {
        p = s.top();
        s.pop();
        p = p->rchild;
    }
}
*/

void preOrder2(BinTree *root) //出栈时打印
{
    stack<BinTree *> s;
    s.push(root);
    while (!s.empty())
    {
        BinTree *cur = s.top();
        cout << cur->data << "";
        s.pop();
        s.push(cur->rchild);
        s.push(cur->lchild);
    }
}

二，中序遍历（非递归）LeetCode94

void inOrder(BinTree *root) //非递归中序遍历
{
    stack<BinTree *> s;
    BinTree *p = root;
    while (p != NULL || !s.empty())
    {
        while (p != NULL)
        {
            s.push(p);
            p = p->lchild;
        }
        if (!s.empty())
        {
            p = s.top();
            cout << p->data << "";
            s.pop();
            p = p->rchild;
        }
    }
}

三，后序遍历（非递归）　LeetCode145　　　

/* 后序遍历非递归版 */
void PostOrderNonRec(Node * node)
{
    if (node == nullptr)
        return;

    Node * pre = nullptr;
    stack<Node*> S;
    S.push(node);

    while (!S.empty())
    {
        node = S.top();

        if ((!node->left && !node->right) ||                    // 第一个输出的必是无左右子的叶子结点，只要第一个结点输出，
            (pre && (pre == node->left || pre == node->right))) // 以后的 pre 就不会是空。此处的判断语句加入一个 pre，只是用来
        {                                                       // 确保可以正确输出第一个结点。
            cout << node->data << " ";  // 左右子都全部输出，再输出当前结点
            pre = node;
            S.pop();
        }
        else
        {
            if (node->right)
                S.push(node->right);  // 先进右子，再进左子，取出来的才是左子
            if (node->left)
                S.push(node->left);
        }
    }
}

四，层序遍历 LeetCode102

//本质上是广度优先搜索，因此会用到queue；dfs会复杂很多，详见leetcode题解

void LevelOrder(Node * node)
{
    Node * p = node;
    queue<Node*> Q;  // 队列
    Q.push(p);
  
    while (!Q.empty())
    {
        p = Q.front();
        cout << p->data << " ";
        Q.pop();
      
        if (p->left)
            Q.push(p->left);  // 注意顺序，先进左子
        if (p->right)
            Q.push(p->right);
    }
}

五，二叉树的节点总数 compare 叶子节点数

//节点总数


int CountNodes(Node * node)
{
    if (node == nullptr)
        return 0;
  
    return CountNodes(node->left) + CountNodes(node->right) + 1;
}

//叶子节点数

int CountLeaves(Node * node)
{
    if (node == nullptr)
        return 0;
  
    if (!node->left && !node->right)
        return 1;
  
    return CountLeaves(node->left) + CountLeaves(node->right);
}

六，二叉树的深度

int GetDepth(Node * node)
{
    if (node == nullptr)
        return 0;
  
    int left_depth = GetDepth(node->left);
    int right_depth = GetDepth(node->right);
  
    return left_depth > right_depth ? left_depth + 1 : right_depth + 1 ；
}

七，第k层的节点个数

int GetKLevel(Node * node, int k)
{
    if (node == nullptr)
        return 0;
  
    if (k == 1)
        return 1;
  
    return GetKLevel(node->left, k - 1) + GetKLevel(node->right, k - 1);
}

八，求两个节点的最低公共祖先节点 LeetCode面试题04.08

Node * FindLCA(Node * node, Node * target1, Node * target2)
{
    if (node == nullptr)
        return nullptr;
    if (node == target1 || node == target2)
        return node;
  
    Node * left = FindLCA(node->left, target1, target2);
    Node * right = FindLCA(node->right, target1, target2);
    if (left && right)  // 分别在左右子树
        return node;
  
    return left ? left : right;  // 都在左子树或右子树
}

九，求任意两节点的距离

//先找到两节点的首个共同祖先，再计算祖先与两节点的距离之和

//根节点与目标子节点的距离
int FindLevel(Node * node, Node * target)
{
    if (node == nullptr)
        return -1;　　//-1代表false
    if (node == target)
        return 0;　　//距离为0
  
    int level = FindLevel(node->left, target);  // 先在左子树找
    if (level == -1)　　//false
        level = FindLevel(node->right, target);  // 如果左子树没找到，在右子树找
  
    if (level != -1)  // 找到了，回溯
        return level + 1;
  
    return -1;  // 如果左右子树都没找到
}
//FindLCA为上一段代码
int DistanceNodes(Node * node, Node * target1, Node * target2)
{
    Node * lca = FindLCA(node, target1, target2);  // 找到最低公共祖先结点
    int level1 = FindLevel(lca, target1); 
    int level2 = FindLevel(lca, target2);
  
    return level1 + level2;
}

十，找出二叉树中某个节点的所有祖先节点

bool FindAllAncestors(Node * node, Node * target)
{
    if (node == nullptr)
        return false;
    if (node == target)
        return true;
  
    if (FindAllAncestors(node->left, target) || FindAllAncestors(node->right, target))  // 找到了
    {
        cout << node->data << " ";
        return true;  // 回溯
    }
  
    return false;  // 如果左右子树都没找到
}

十一，判断二叉树是否为完全二叉树

//若某个节点只有右节点，结果为false；若某个节点只有左节点或无子节点，则改行中剩下节点无子节点，否则为false
//flag标记变量
bool IsCBT(Node * node)
{
    bool flag = false;
    queue<Node*> Q;
    Q.push(node);
  
    while (!Q.empty())
    {
        Node * p = Q.front();
        Q.pop();
      
        if (flag)
        {
            if (p->left || p->right)
                return false;
        }
        else
        {
            if (p->left && p->right)
            {
                Q.push(p->left);
                Q.push(p->right);
            }
            else if (p->right)  // 只有右结点
                return false;
            else if (p->left)   // 只有左结点
            {
                Q.push(p->left);
                flag = true;
            }
            else  // 没有结点
                flag = true;
        }
    }
  
    return true;
}

原文链接