二叉树

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

二叉树的定义和结构

1
2
3
4
5
6
7
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

=>根节点是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

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

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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);
}
//最终用于调用
};

中序遍历代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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;
}

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

例子和调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}

这棵树为

     3
    / \
   9  20
     /  \
    15   7

二叉树的最大深度

递归+最大值

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

最大路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
//返回加上根节点一共的最大值
}