二叉树的遍历

二叉树

二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

二叉树的定义和结构

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

以存储int值为数据的二叉树为例,每一个二叉树节点有一个左节点和右节点,故以此建立树节点的结构体,初识孩子指针为NULL。

二叉树从前序和中序遍历建树

主要思想

    A
   / \
  B   C
 / \
D   E

如上二叉树:
前序遍历为 ABDEC
中序遍历为 DBEAC

不难发现，在这两种遍历中，以前序遍历的顺序在中序遍历中寻找对应节点。
在找到该节点后，其中序遍历左侧的即为左子树，右侧即为右子树。

原理讲解

Step 1:
ABDEC
DBEAC

目前的树：

=>根节点是A，现在考虑左子树
Step 2:
ABDEC
DBE

目前的树：

    A
   /
  B

=>根节点是B，现在考虑左子树
Step 3:
ABDEC
D
=>叶子节点D

目前的树：

    A
   /
  B
 /
D

=>根节点是B，现在考虑右子树
Step 4:
ABDEC
E
=>叶子节点E

目前的树：

    A
   /
  B
 / \
D   E

=>根节点是A，现在考虑右子树
Step 5:
ABDEC
C
=>叶子节点C

目前的树：

    A
   / \
  B   C
 / \
D   E

不难发现，以上过程可以利用递归实现
**需要的参数为：**中序遍历中的某一段(相当于一个头和尾巴)
**需要的全局变量为：**标记前序遍历位数的变量

代码实现

class Solution
{
  private:
    int flag = 0;
    //前序遍历当前查询位置

  public:
    TreeNode *Build_for_pre_in(int begin, int end, vector<int> &preorder, vector<int> &inorder)
    {
        if (begin > end)
            return NULL;
        //到达叶子节点继续访问会出现这种情况
        //等价于无子节点

        TreeNode *t_node = new TreeNode(-1);
        if (begin == end)
        {
            t_node->val = inorder[begin];
            flag++;
            return t_node;
        }
        //此处是到达叶子节点的访问和赋值


        for (int i = begin; i <= end; i++)
        {
            if (inorder[i] == preorder[flag])
            //如果找到中序和前序某一位相同
            {
                t_node->val = inorder[i];
                flag++;
                t_node->left = Build_for_pre_in(begin, i - 1, preorder, inorder);
                //找左子树
                t_node->right = Build_for_pre_in(i + 1, end, preorder, inorder);
                //找右子树
                break;
            }
        }
        //在一般情况下匹配中序和前序

        return t_node;
    }

    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
    {
        return Build_for_pre_in(0, inorder.size() - 1, preorder, inorder);
    }
    //最终用于调用
};

中序遍历代码实现

vector<int> inorderTraversal(TreeNode *root)
{
    vector<int> a, b, c;
    if (root == NULL)
        return a;
    //再次递归是子节点调用即返回空数组

    b = inorderTraversal(root->left);
    a.insert(a.begin(), b.begin(), b.end());
    //这两行为“左”

    a.push_back(root->val);
    //此行为“根”

    c = inorderTraversal(root->right);
    a.insert(a.end(), c.begin(), c.end());
    //这两行为“右”

    return a;
}

前序遍历：根左右
中序遍历：左根右
后序遍历：左右根
将上述程序中的“左”“根”“右”再次组合即可写出相应遍历程序。

例子和调用

int main()
{
    Solution *obj = new Solution();
    vector<int> pre = {3, 9, 20, 15, 7};
    vector<int> in = {9, 3, 15, 20, 7};
    TreeNode *root = obj->buildTree(pre, in);
    vector<int> out = obj->inorderTraversal(root);
    for(int i = 0; i < out.size(); i++)
    {
        cout<<out[i]<<" ";
    }
    system("pause");
    return 0;
}

这棵树为

二叉树的最大深度

递归+最大值

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

最大路径和

int maxPathSum(TreeNode* root)
{
    int ans = -100000;
    path(root,ans);
    return ans;
}

int path(TreeNode *root,int &res)
{
    if(root==NULL) return 0;
    //叶子节点不再继续访问
    int left = path(root->left,res);
    //左子树最大路径
    int right = path(root->right,res);
    //右子树最大路径
    int maxl = max(left,right);
    if(maxl<0) maxl = 0;
    //取最大正值

    res = max(res,(left>0?left:0)+(right>0?right:0)+root->val);
    //子树>0则表示向下可取
    //以该节点为根的子树最长路径和目前已存最大路径中的较大值

    return maxl+root->val;
    //返回加上根节点一共的最大值
}