二叉树今生
为什么会有二叉树这种数据结构？
思考一个问题：如果一个集合中有42亿个元素，让你从这42亿个元素中搜索某一个元素，你需要多少次操作？
如果使用数组链表的话最多可能需要42亿次比较，而如果使用二叉树我们只需要32次比较即可，这就是二叉树存在的价值。Java中的HashSet使用的就是二叉树
前驱与后继
前驱节点
若一个节点有左子树，那么该节点的前驱节点是其左子树中val值最大的节点（也就是左子树中所谓的rightMostNode）
若一个节点没有左子树，那么判断该节点和其父节点的关系
2.1 若该节点是其父节点的右边孩子，那么该节点的前驱结点即为其父节点。
2.2 若该节点是其父节点的左边孩子，那么需要沿着其父亲节点一直向树的顶端寻找，直到找到一个节点P，P节点是其父节点Q的右边孩子（可参考例子2的前驱结点是1），那么Q就是该节点的后继节点
后继节点
- 若一个节点有右子树，那么该节点的后继节点是其右子树中val值最小的节点（也就是右子树中所谓的leftMostNode）
- 若一个节点没有右子树，那么判断该节点和其父节点的关系
2.1 若该节点是其父节点的左边孩子，那么该节点的后继结点即为其父节点
2.2 若该节点是其父节点的右边孩子，那么需要沿着其父亲节点一直向树的顶端寻找，直到找到一个节点P，P节点是其父节点Q的左边孩子（可参考例子2的前驱结点是1），那么Q就是该节点的后继节点
如何判断两个二叉树是否相同？
递归法
1
2
3
4
5
6
7
8
9
10
11
12
| static public bool IsSameTree(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) {
return true;
}
if ((root1 == null && root2 != null) || (root1 != null && root2 == null)) {
return false;
}
if (root1.val != root2.val) {
return false;
}
return IsSameTree(root1.left, root2.left) && IsSameTree(root1.right, root2.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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| bool BTreeCompare（BTreeNode_t *pRoot1, BTreeNode_t *pRoot2)
{
if( pRoot1 == NULL && pRoot2 == NULL )
return false;
queue <BTreeNode_t *> que1;
queue <BTreeNode_t *> que2;
que1.push(pRoot1);
que2.push(pRoot2);
int curLevelNodeTotal1 = 0;
int curLevelNodeTotal2 = 0;
bool flag = true;
while( ( !que1.empty()) && ( !que2.empty()))
{
curLevelNodeTotal1 = que1.size();
curLevelNodeTotal2 = que2.size();
if( curLevelNodeTotal1 != curLevelNodeTotal2){
flag = false;
break;
}
int cnt1 = 0;
int cnt2 = 0;
while( cnt1 < curLevelNodeTotal1 && cnt2 < curLevelNodeTotal2){
++cnt1;
++cnt2;
pRoot1 = que1.front();
que1.pop();
pRoot2 = que2.front();
que2.pop();
if( pRoot1->m_pElemt != pRoot2->m_pElemt ){
flag = false;
break;
}
if( ( pRoot1->m_pLeft != NULL && pRoot2->m_pLeft == NULL ) ||
( pRoot1->m_pLeft == NULL && pRoot2->m_pLeft != NULL ) ||
( pRoot1->m_pRight != NULL && pRoot2->m_pRight == NULL ) ||
( pRoot1->m_pRight == NULL && pRoot2->m_pRight != NULL )
){
flag = false;
break;
}
if( pRoot1->m_pLeft != NULL )
que1.push( pRoot1->m_pLeft);
if( pRoot1->m_pRight != NULL )
que1.push( pRoot1->m_pRight);
if( pRoot2->m_pLeft != NULL )
que2.push( pRoot2->m_pLeft);
if( pRoot2->m_pRight != NULL )
que2.push( pRoot2->m_pRight);
}
if( flag == false )
break;
}
if( flag == false ){
while( !que1.empty() )
que1.pop();
while( !que2.empty())
que2.pop();
return false;
}
return true;
}
|
