This article has been machine-translated from Chinese. The translation may contain inaccuracies or awkward phrasing. If in doubt, please refer to the original Chinese version.

Problem Set Master Index Study blogs linked: Binary Trees, Queues

03-Tree 1 Isomorphism of Trees (25 pts)

Problem Link

The beginner’s session will provide a detailed explanation. This is a basic requirement and must be done. > Problem description: Given two trees, determine whether they are isomorphic.

Approach

1. Representation of binary trees Use arrays to store structs, where each struct contains data and the indices of left and right children (Null represents -1). 2. Build the binary tree Return the root node index. 3. Isomorphism check Use recursion. If both R1 and R2 are empty, return true. If one of them is empty, return false. If the root elements are different, return false. Then check the left and right subtrees: if both left subtrees are empty, check whether the right subtrees are isomorphic. If both left subtrees are non-empty and have the same element, no swap is needed — check directly. Otherwise, swap and check.

Code

#include <iostream>
using namespace std;
#define maxsize 11
#define Null -1
typedef int Tree;
struct TNode {
    char data;
    Tree left,right;
}T1[maxsize], T2[maxsize];
Tree BuildTree(struct TNode T[]){
    int N,root;
    char l,r;
    bool isroot[maxsize];
    root = Null;
    scanf("%d", &N);
    if(N) {
        for(int i = 0; i < N; ++i) isroot[i] = true;
        getchar();
        for(int i = 0; i < N; ++i) {
            scanf("%c %c %c", &T[i].data, &l, &r);
            getchar();
            if(l != '-') {
                T[i].left = l -'0';
                isroot[T[i].left] = false;
            } else T[i].left = Null;
            if(r != '-') {
                T[i].right = r -'0';
                isroot[T[i].right] = false;
            } else T[i].right = Null;
        }
        for(int i = 0; i < N; ++i)
            if(isroot[i]) {
                root = i;
                break;
            }
    }
    return root;
}
bool judge(Tree R1, Tree R2) {
    if(R1 == Null && R2 == Null)
        return true;    //两个都为空
    if((R1 == Null && R2 != Null) || (R1 != Null && R2 == Null))
        return false;   //其中一个为空
    if(T1[R1].data != T2[R2].data)
        return false;   //根节点元素就不一样
    //两个左子树都为空，则判断右子树是否同构
    if(T1[R1].left == Null && T2[R2].left == Null)
        return judge(T1[R1].right, T2[R2].right);
    //两个左子树都不为空且元素相同，不用交换
    if((T1[R1].left != Null) && (T2[R2].left != Null)
            && (T1[T1[R1].left].data == T2[T2[R2].left].data))
        return judge(T1[R1].left, T2[R2].left) &&
            judge(T1[R1].right, T2[R2].right);
    else {//交换左右子树，判断
        return judge(T1[R1].left, T2[R2].right) &&
               judge(T1[R1].right, T2[R2].left);
    }
}
int main() {
    Tree R1, R2;
    R1 = BuildTree(T1);
    R2 = BuildTree(T2);
    if(judge(R1, R2))
        cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Test Cases

Test cases are as follows

03-Tree 2 List Leaves (25 pts)

Problem Link

Trains the fundamentals of tree construction and traversal, must be done

Problem Description

Given a tree, you should list all leaf nodes in top-down, left-to-right order.

Approach

To output leaf nodes in top-down, left-to-right order, a level-order traversal is needed. The overall code is largely the same as problem 3-1.

#include <iostream>
#include <queue>
using namespace std;
#define maxsize 11
#define Null -1
typedef int Tree;
int cnt;
struct TNode {
    int data;
    Tree left,right;
}T1[maxsize];
Tree BuildTree(struct TNode T[]){
    int N,root;
    char l,r;
    bool isroot[maxsize];
    root = Null;
    scanf("%d", &N);
    if(N) {
        for(int i = 0; i < N; ++i) isroot[i] = true;
        getchar();
        for(int i = 0; i < N; ++i) {
            scanf("%c %c", &l, &r);
            getchar();
            if(l != '-') {
                T[i].left = l -'0';
                isroot[T[i].left] = false;
            } else T[i].left = Null;
            if(r != '-') {
                T[i].right = r -'0';
                isroot[T[i].right] = false;
            } else T[i].right = Null;
        }
        for(int i = 0; i < N; ++i)
            if(isroot[i]) {
                root = i;
                break;
            }
    }
    return root;
}
void LevelOrderTraversal(Tree R) {
    queue<Tree> q; //保存暂不访问的节点
    if(R == Null) return;
    q.push(R);
    while(!q.empty()) {
        Tree R1 = q.front();
        q.pop();
        if(T1[R1].left == Null && T1[R1].right == Null) {//为叶子结点
            if(cnt != 0) {
                printf(" %d", R1);
            } else printf("%d",R1);
            cnt++;
        }
        if(T1[R1].left != Null) {
            q.push(T1[R1].left);
        }
        if(T1[R1].right != Null) {
            q.push(T1[R1].right);
        }
    }

}
int main() {
    int N;
    Tree R1, R2;
    R1 = BuildTree(T1);
    LevelOrderTraversal(R1);
    return 0;
}

Test cases are as follows, passed on the first try

03-Tree 3 Tree Traversals Again (25 pts)

Problem Link

This is a 2014 Fall PAT Level A exam problem. It requires some thinking, but once you figure it out, the program is quite basic. Recommended to try.

Problem Description

Given the push and pop sequences, which are the preorder and inorder traversal sequences of a binary tree, find the postorder traversal sequence.

Approach

This can be implemented recursively! First extract both sequences, reconstruct the binary tree, then perform postorder traversal.

#include <iostream>
#include <stack>
#include <queue>
using namespace std;
#define maxsize 35
#define Null -1
int N, x, pcnt,icnt,cnt;
typedef int Tree;
struct TNode {
    int data;
    Tree left,right;
}T1[maxsize];
string o;
stack<char> s;
int c2i(char ch) {
    return ch - '0';
}
Tree Rebuild(string pre,string in) {  //已知前序和中序，求这棵树
    Tree R;
    if(pre.empty() && in.empty()) return Null;
    R = c2i(pre[0]);
    int l, r, Rindex,len;
    len = pre.length();
    Rindex = in.find(pre[0],0); //中序遍历中根节点的下标
    l = Rindex;  //左子树序列的长度
    r = len - 1 - Rindex;  //右子树序列的长度
    if (Rindex != 0)     //存在左子树
        T1[R].left = Rebuild(pre.substr(1,l), in.substr(0, l));
    else T1[R].left = Null;
    if (Rindex != len-1)   //存在右子树
        T1[R].right = Rebuild(pre.substr(Rindex + 1, r), in.substr(Rindex + 1, r));
    else T1[R].right = Null;
    return R;
}
void PostOrderTraversal(Tree R) {
    if (R == Null) return;
    PostOrderTraversal(T1[R].left);
    PostOrderTraversal(T1[R].right);
    if(cnt == 0) cout << R;
    else cout << " " << R;
    cnt++;
}
int main() {
    string preod,inod;
    char ch;
    cin >> N;
    getchar();
    int n = 2*N;
    for(int i = 0; i < n; ++i) {
        cin >> o;
        if(o == "Push") {   //前序
            cin >> x;
            ch = x + '0';
            s.push(ch);
            preod = preod + ch;
        } else {    //中序
            inod = inod + s.top();
            s.pop();
        }
        getchar();
    }
    Tree R1;
    R1 = Rebuild(preod, inod);
    PostOrderTraversal(R1);
    cout << endl;
    return 0;
}

Test Cases

Test cases are as follows