欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树相关代码学习记录

程序员文章站 2022-06-05 18:59:35
...

一、二叉树的遍历

二叉树的基本遍历方法有: 前序遍历、中序遍历、后续遍历和层次遍历。
代码:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

void preorder_print(TreeNode *node, int layer)
{
    if (!node)
        return;
    //根据层数,打印相应数量的"--"
    for (int i = 0; i < layer; ++i)
        cout << "---";

    cout << "[" << node->val << "]\n";
    preorder_print(node->left, layer + 1); //遍历左子树
    preorder_print(node->right, layer + 1);//遍历右子树
}

//非递归版本
//先访问根,然后依次将右节点、左节点放到栈中
void preOrder(TreeNode * root)
{
    if (root == NULL) return;
    stack<TreeNode *> st;
    st.push(root);
    while (!st.empty())
    {
        TreeNode *temp = st.top();
        st.pop();
        cout << temp->val << " ";

        //利用栈的特性,先把右节点放入
        if (temp->right != NULL)
            st.push(temp->right);
        if (temp->left != NULL)
            st.push(temp->left);
    }
    cout << endl;
}



void inorder_print(TreeNode *node, int layer)
{
    if (!node)
        return;
    inorder_print(node->left, layer + 1); //遍历左子树

    //根据层数,打印相应数量的"--"
    for (int i = 0; i < layer; ++i)
        cout << "---";

    cout << "[" << node->val << "]\n";

    inorder_print(node->right, layer + 1);//遍历右子树
}

//非递归版本

//根据中序遍历的顺序,对于任意节点,优先访问其左孩子,而左孩子节点又可以看做一根节点,然后继续访问左孩子节点为空的节点才进行
//访问,然后按相同的规则访问其右子树。因此其处理过程如下:
//(1)对于任意节点其左孩子不为空,则将P入栈并将P的左孩子置为当前的P,然后对当前节点P再进行相同的处理
//(2)若其左孩子不为空,则取栈顶元素并进行出栈操作,访问该栈顶节点,然后将当前的P置为栈顶节点的右孩子
//(3)直到P为NULL并且栈为空则遍历结束

void inOrder(TreeNode * root)
{
    if (root == NULL) return;
    stack<TreeNode *> st;
    TreeNode * pNode = root;
    while (pNode != NULL || !st.empty())
    {
        while (pNode != NULL)
        {
            st.push(pNode);
            pNode = pNode->left;
        }
        if (!st.empty())
        {
            pNode = st.top();
            st.pop();
            cout << pNode->val << " ";

            pNode = pNode->right;
        }

    }

    cout << endl;
}



void postorder_print(TreeNode *node, int layer)
{
    if (!node)
        return;
    postorder_print(node->left, layer + 1); //遍历左子树
    postorder_print(node->right, layer + 1);//遍历右子树

    //根据层数,打印相应数量的"--"
    for (int i = 0; i < layer; ++i)
        cout << "---";

    cout << "[" << node->val << "]\n";

}

void level_print(TreeNode *node)
{
    if (!node)
        return;
    queue<TreeNode *> qu;
    qu.push(node);
    while (!qu.empty())
    {
        TreeNode * temp = qu.front();
        qu.pop();
        cout << temp->val << " ";
        if (temp->left != NULL)
            qu.push(temp->left);
        if (temp->right != NULL)
            qu.push(temp->right);
    }
    cout << endl;
}
//层次遍历的第二种方法
vector<vector<int> > levelOrder(TreeNode *root) {
    vector<vector<int> > res;
    if (root == NULL) return res;

    queue<TreeNode *> qu;
    qu.push(root);
    while (!qu.empty())
    {
        int level = qu.size();
        vector<int> levelPath;
        for (int i = 0; i < level; ++i)
        {
            TreeNode * temp = qu.front();
            qu.pop();
            //cout << temp->val << " ";
            levelPath.push_back(temp->val);
            if (temp->left != NULL)
                qu.push(temp->left);
            if (temp->right != NULL)
                qu.push(temp->right);
        }
        //将每一层加入结果集res中
        res.push_back(levelPath);
    }

    return res;

}
-------------------------------------------
//层次遍历的第二种方法添加如下代码即修改为之字形遍历
//也就是在每一层求得的结果在插入结果集之前根据奇偶层反转即可
if (res.size() % 2 != 0)
{
    reverse(levelPath.begin(), levelPath.end());
}

测试:


/*
      1
   2     5
3    4      6
*/
int main()
{

    TreeNode a(1);
    TreeNode b(2);
    TreeNode c(3);
    TreeNode d(4);
    TreeNode e(5);
    TreeNode f(6);

    a.left = &b;
    a.right = &e;
    b.left = &c;
    b.right = &d;
    e.right = &f;

    int layer = 0;
    cout << "preoder thee" << endl;
    preorder_print(&a, layer);
    cout << "inorder thee" << endl;
    inorder_print(&a, layer);
    cout << "postorder thee" << endl;
    postorder_print(&a, layer);
    cout << "level thee" << endl;
    level_print(&a);
}

二、路径之和

给定一个二叉树与整数sum,判断所有与根节点到叶节点的路径是否存在累加和为sum。

bool hasPathSum(TreeNode *root, int sum) {

    if (root == NULL) return false;

    if (root->left == NULL && root->right == NULL && root->val == sum)
    {
        //满足条件时返回true
        return true;
    }
    if (root->left !=NULL &&  hasPathSum(root->left, sum - root->val))
        return true;
    if (root->right != NULL && hasPathSum(root->right, sum - root->val))
        return true;

    return false;
}

三、路径之和2

给定一个二叉树与整数sum,找出所有与根节点到叶节点的路径,这些路径上的结点值累加和为sum。
二叉树相关代码学习记录
输出:
[
[5,4,11,2],
[5,8,4,5]
]
代码:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

void pathSumCore(TreeNode *root, int sum, int &curSum, vector<int> &path_val, vector<vector<int> > &res) {
    if (root == NULL) return;

    path_val.push_back(root->val);
    curSum += root->val;
    if (root->left == NULL && root->right == NULL && curSum == sum)
    {
        #if 0
        for (vector<int>::iterator it = path_val.begin(); it != path_val.end(); ++it)
            cout << *it << " ";
        cout << endl;
        #endif
        //将满足条件的路径push到结果集合res中
        res.push_back(path_val);
    }

    pathSumCore(root->left, sum, curSum, path_val,res);
    pathSumCore(root->right, sum, curSum, path_val, res);

    //当前节点退回至父节点时,将该数据去除
    curSum -= root->val;
    path_val.pop_back(); 
}


vector<vector<int> > pathSum(TreeNode *root, int sum) {
    vector<vector<int> > res;
    if (root == NULL) return res;

    int curSum = 0;
    vector<int> path_val;
    pathSumCore(root, sum, curSum,path_val,res);

    return res;
}

int main()
{

    TreeNode a(5);
    TreeNode b(4);
    TreeNode c(8);
    TreeNode d(11);
    TreeNode e(13);
    TreeNode f(4);
    TreeNode g(7);
    TreeNode h(2);
    TreeNode i(5);
    TreeNode j(1);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    d.left = &g;
    d.right = &h;
    c.left = &e;
    c.right = &f;
    f.left = &i;
    f.right = &j;

    int sum = 22;
    vector<vector<int> > res =pathSum(&a, sum);
    for (vector<vector<int>>::iterator ite = res.begin(); ite != res.end(); ite++)
    {
        vector<int> temp_vect = *ite;
        for (vector<int>::iterator itee = temp_vect.begin(); itee != temp_vect.end(); itee++)
            cout << *itee << " ";
        cout << endl;
    }
}

四、根据前序和中序重建二叉树

方法一:使用额外空间

    TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
    if (pre.empty() || vin.empty()) return NULL;
    int size = pre.size(); //等于vin.size()
    int index = 0;
    for (; index < size; ++index)
    {
        if (vin[index] == pre[0])
            break;
    }
    vector<int> pre_left, pre_right, vin_left, vin_right;
    //找出前序、中序序列中的左子树
    for (int i = 0; i < index; ++i)
    {
        pre_left.push_back(pre[i + 1]);
        vin_left.push_back(vin[i]);
    }
    //找出前序、中序序列中的右子树
    for (int j = index + 1; j < size; ++j)
    {
        pre_right.push_back(pre[j]);
        vin_right.push_back(vin[j]);
    }
    //构造根节点
    TreeNode *root = new TreeNode(pre[0]);
    root->left = reConstructBinaryTree(pre_left, vin_left);
    root->right = reConstructBinaryTree(pre_right, vin_right);

    return root;
}

方法二:不适用额外空间

    TreeNode* reConstructBinaryTree(vector<int> &pre, vector<int> &vin, int startPre, int endPre, int startInorder, int endInorder) {

    int rootVal = pre[startPre];
    //构造根节点
    TreeNode *root = new TreeNode(rootVal);
    if (endPre == startPre || endInorder == startInorder) return root;

    int index = startInorder;
    for (; index <= endInorder; ++index)
    {
        if (vin[index] == rootVal)
            break;
    }

    //左子树元素个数,右子树元素个数均根据中序遍历来找
    int leftLength = index - startInorder;
    int rightLength = endInorder - index;

    if (leftLength>0)
        root->left = reConstructBinaryTree(pre, vin, startPre + 1, startPre + leftLength, startInorder, index - 1);  //startPre + leftLength
    if (rightLength>0)
        root->right = reConstructBinaryTree(pre, vin, startPre + leftLength + 1, endPre, index + 1, endInorder);

    return root;
}

TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
    if (pre.empty() || vin.empty() || pre.size() != vin.size() ) return NULL;
    int size = pre.size(); //等于vin.size()

    return reConstructBinaryTree(pre, vin, 0, size - 1, 0, size - 1);
}