首页 > 代码库 > Chap4: question: 19 - 28

Chap4: question: 19 - 28

2024-07-02 05:34:21   223人阅读

19. 二叉树的镜像（递归）

 即：交换所有节点的左右子树。从下往上 或 从上往下 都可以。

+ View Code?
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
#include <iostream>
#include <string>
using namespace std;
struct BTNode
{
    int v;  // default positive Integer.
    BTNode *pLeft;
    BTNode *pRight;
    BTNode(int x) : v(x), pLeft(NULL), pRight(NULL) {}
};
/********************************************************/
/*****        Basic functions          ***********/
BTNode* createBinaryTree(int r)
{
    BTNode *pRoot = new BTNode(r);
    int u, v;
    cin >> u >> v;
    if(u != 0)
        pRoot->pLeft = createBinaryTree(u);
    if(v != 0)
        pRoot->pRight = createBinaryTree(v);
    return pRoot;
}
void release(BTNode *root){
    if(root == NULL) return;
    release(root->pLeft);
    release(root->pRight);
    delete[] root;
    root = NULL;
}
void print(BTNode *root, int level = 1){
    if(root == NULL) { cout << "NULL"; return; };
    string s;
    for(int i = 0; i < level; ++i) s += "   ";
    cout << root->v << endl << s;
    print(root->pLeft, level+1);
    cout << endl << s;
    print(root->pRight, level+1);
}
/******************************************************************/
void mirrorTree(BTNode *root)
{
    if(!root || (!root->pLeft && !root->pRight)) return;
    /*    交换左右子树           */
    BTNode *pTem = root->pLeft;
    root->pLeft = root->pRight;
    root->pRight = pTem;
 
    mirrorTree(root->pLeft);
    mirrorTree(root->pRight);
}
 
 
int main(){
    int TestTime = 3, k = 1;
    while(k <= TestTime)
    {
        cout << "Test " << k++ << ":" << endl;
         
        cout << "Create a tree: " << endl;
        BTNode *pRoot = createBinaryTree(8);
        print(pRoot);
        cout << endl;
 
        cout << "The mirror tree: " << endl;
        mirrorTree(pRoot);
        print(pRoot);
        cout << endl;
 
        release(pRoot);
    }
    return 0;
}

 

 20. 顺时针打印矩阵

 1 #include <stdio.h>
 2 
 3 void printMatrix(int (*A)[1], int rows, int columns)
 4 {
 5     if(rows < 1 || columns < 1) return;
 6     int r1, r2, c1, c2;
 7     r1 = c1 = 0, r2 = rows-1, c2 = columns-1;
 8     while(r1 <= r2 && c1 <= c2) /* 打印结束时， r1 = r2+1, c1 = c2+1; */
 9     {
10         for(int i = c1; i <= c2 && r1 <= r2; ++i)
11             printf("%d ", A[r1][i]);
12         ++r1;
13         for(int i = r1; c1 <= c2 && i <= r2; ++i)
14             printf("%d ", A[i][c2]);      /*   要保证 c1 <= c2  */      
15         --c2;
16         for(int i = c2; i >= c1 && r1 <= r2; --i)
17             printf("%d ", A[r2][i]);
18         --r2;
19         for(int i = r2; i >= r1 && c1 <= c2; --i)
20             printf("%d ", A[i][c1]);
21         ++c1;
22     }
23     printf("\n");
24 }
25 int main()
26 {
27     int test1[3][3] = {{1, 2, 3},
28                        {4, 5, 6}, 
29                         {7, 8, 9}};
30     printMatrix(test1, 3, 3);
31 
32     int test2[1][3] = {1, 2, 3};
33     printMatrix(test2, 1, 3);
34 
35 /*  // first set int (*A)[1], then began called below. 
36     int test3[3][1] = {{1}, {2}, {3}};
37     printMatrix(test3, 3, 1);
38 
39     int test4[1][1] = {1};
40     printMatrix(test4, 1, 1);
41 */
42     return 0;
43 }
View Code

      （）

 21. 包含 min  函数的栈

 要求调用 min，pop，push，时间复杂度都是 O(1)。

 1 #include <iostream>
 2 #include <stack>
 3 #include <cassert>
 4 #include <string>
 5 template<typename T> class Stack
 6 {
 7 public:
 8     void push(T value);
 9     void pop();
10     T min();
11 private:
12     std::stack<T> data;
13     std::stack<T> minData;
14 };
15 template<typename T> void Stack<T>::push(T value)
16 {
17     data.push(value);
18     if(minData.empty() || minData.top() >= value)
19         minData.push(value);
20     else
21         minData.push(minData.top());
22 }
23 template<typename T> void Stack<T>::pop()
24 {
25     assert(data.size() > 0 && minData.size() > 0);
26     data.pop();
27     minData.pop();
28 }
29 template<typename T> T Stack<T>::min()
30 {
31     return minData.top();
32 }
33 
34 int main()
35 {
36     Stack<char> st;
37     std::string numbers;
38     while(std::cin >> numbers)
39     {
40         for(size_t i = 0; i < numbers.length(); ++i) st.push(numbers[i]);
41         for(size_t i = 0; i < numbers.length(); ++i)
42         {
43             std::cout << "st.min(): " << st.min() << std::endl;
44             st.pop();
45         }
46     }
47     return 0;
48 }
View Code

22. 根据栈的压入序列，判断一个序列是否是弹出序列。 

+ View Code?
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
#include <iostream>
#include <string>
 
bool isPopOrder(const std::string pushS, const std::string popS)
{
    size_t outId1 = 0, outId2 = 0, len1 = pushS.length(), len2 = popS.length();
    if(len1 != len2) return false;
    int *stack = new int[len1];
    int tail = 0; // 栈尾
    while(outId1 < len1 && outId2 < len2)
    {
        while(pushS[outId1] != popS[outId2])
        {
            stack[tail++] = pushS[outId1++]; // 入栈
        }
        outId1++, outId2++;
        while(tail != 0 && popS[outId2] == stack[tail-1])
        {
            ++outId2;
            tail--;     // 出栈
        }
    }
    delete[] stack;
    if(tail == 0) return true; // 栈空
    else return false;
}
 
int main()
{
    std::string numbers;
    std::string popNumbers;
    while(std::cin >> numbers >> popNumbers)
    {
        std::cout << "一个弹出序列?   " ;
 
        if(isPopOrder(numbers, popNumbers))
            std::cout << "true" << std::endl;
        else std::cout << "false" << std::endl;
    }
    return 0;
}

 

23. 从上往下打印二叉树

 Go:（Chap2: question: 1 - 10—>6. 重建二叉树—>二叉树的各种遍历）Link: http://www.cnblogs.com/liyangguang1988/p/3667443.html

24. 判断序列是否为二叉搜索树的后序遍历（递归）

note: 二叉搜索树和遍历序列一一对应。

例：后序序列 {3，5，4，6，11，13，12, 10, 8} ，可画出一颗二叉搜索树。

 1 #include <iostream> 
 2 /* verify the seq which should be the postOrder of a Binary Search Tree  */
 3 bool postOrderOfBST(int sequence[], int len)
 4 {
 5     if(sequence == NULL || len == 0) return false;
 6     bool answer = false;
 7     int root = sequence[len-1];    /* value of root node */
 8 
 9     int leftLength = 0;
10     for(; leftLength < len-1; ++leftLength)
11     {
12         if(sequence[leftLength] > root) break;
13     }
14     /*  verify right-subtree, should big than root  */
15     for(int i = leftLength + 1; i < len -1; ++i)
16     {
17         if(sequence[i] < root) return false;
18     }
19 
20     int rightLength = len - 1 - leftLength;
21     bool left = true, right = true;
22     if(leftLength > 0)
23         bool left = postOrderOfBST(sequence, leftLength);
24     if(rightLength)
25         bool right = postOrderOfBST(sequence+leftLength, rightLength);
26     return (left && right);
27 }
28 
29 void printResult(bool v)
30 {
31     std::cout << "Is LRD of a BFS?  " ; 
32     if(v)  std::cout << "true" << std::endl;
33     else  std::cout << "false" << std::endl; 
34 }
35 int main() 
36 {
37     std::cout << "Test 1: ";
38     int test1[] = {3, 5, 4, 6, 11, 13, 12, 10, 8};
39     printResult(postOrderOfBST(test1, sizeof(test1) / 4)) ;
40 
41     std::cout << "Test 2: ";
42     int test2[] = {4, 2, 3}; 
43     printResult(postOrderOfBST(test2, sizeof(test2) / 4)); 
44         
45     std::cout << "Test 3: ";
46     int test3[] = {1};
47     printResult(postOrderOfBST(test3, sizeof(test3) / 4));
48 
49     return 0; 
50 }
View Code

 25. 二叉树中和为某一值的路径

 

 

 

 

 

 

 

 


联系
我们