二叉树相关代码学习记录

一、二叉树的遍历

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

#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);
}