1.树的同构

Problem
判断给定两棵树T1和T2是否同构。详细描述

Analysys

构建树的结构体数组表示，下标指向左右儿子的所在位置。
确定树根，用一个check数组保存当前节点有没有被指向，没有被指向的节点为根节点。
判断一棵树是否同构，三种情况：两棵树是否有空树，返回两者是否都为空的并集；两棵树当前节点元素值不同，不同构返回false；否则，树T1，T2的左子树 && T1，T2的右子树是否同时同构或者T1左子树 || T2右子树 && T1左子树，T2右子树是否同时同构。根据上述条件递归调用进行判断。

Code

#include <stdio.h>
using namespace std;

#define MaxTree 10
#define ElementType char
#define Tree int
#define Null -1

struct TreeNode{
    ElementType data;
    Tree left;
    Tree right; 
}T1[MaxTree], T2[MaxTree];

Tree buildTree(TreeNode T[]) {
    int N;
    ElementType cl, cr, root;
    int check[MaxTree];
    scanf("%d\n", &N);
    if(N) {
        // 初始化每个节点，设没有被指向时值为0 
        for(int i = 0; i < N; i++) check[i] = 0; 
        // 建树 
        for(int i = 0; i < N; i++) {
            scanf("%c %c %c\n", &T[i].data, &cl, &cr);
            // 对左子树处理 
            if(cl != '-') {
                T[i].left = cl - '0';
                check[T[i].left] = 1;
            } else {
                T[i].left = Null;
            }
            
            // 对右子树处理
            if(cr != '-') {
                T[i].right = cr - '0';
                check[T[i].right] = 1;
            } else {
                T[i].right = Null;
            }
            
            //printf("%c %c %c\n", T[i].data, cl, cr);
        }
        // 遍历找出没有任何节点指向的节点，则其为根节点 
        for(int i = 0; i < N; i++) {
            //printf("%d ", check[i]);
            if(check[i] == 0) {
                root = i;
                break; 
            }
            
        } 
    } else {
        root = Null;
    }
    //printf("%d\n", root);
    return root;
}


// 判断是否同构
bool Isomorphism(Tree R1, Tree R2){
    if(R1 == Null || R2 == Null) {
        return (R1 == Null) && (R2 == Null);
    } else if (T1[R1].data != T2[R2].data){
        return false;
    } else {
        return Isomorphism(T1[R1].left, T2[R2].left) && Isomorphism(T1[R1].right, T2[R2].right)
                || Isomorphism(T1[R1].left, T2[R2].right) && Isomorphism(T1[R1].right, T2[R2].left);
    }
} 

int main() {
    Tree R1, R2; 
    
    #ifndef ONLINE_JUDGE
    freopen("Isomorphism.txt", "r", stdin);
    #endif
    
    // 建立树1
    R1 = buildTree(T1);
    // 建立树2
    R2 = buildTree(T2);
    // 判断是否同构
    if(Isomorphism(R1, R2)) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;   
}

2.List Leaves

Problem
Given a tree, you are supposed to list all the leaves in the order of top down, and left to right.详细描述

Analysys

叶子结点打印按照层次遍历打印，判断左右子树为空时输出叶子节点。
树的问题可考虑数组还是链表两种存储方式，然后基于遍历和堆栈以及队列以及条件对树进行相关操作。

Code

#include <stdio.h>
#include <queue>
using namespace std;

#define MaxSize 10

typedef char ElementType; 
struct TreeNode {
    int left;
    int right;  
}Tr[MaxSize];

// 建树，返回根节点
int builTree(TreeNode T[]) {
    int N; 
    char cl, cr;
    int root;
    scanf("%d\n", &N);
    int check[N];
    if(N) {
        for(int i = 0; i < N; i++) {
            check[i] = 0;
        }
        for(int i = 0; i < N; i++) {
            scanf("%c %c\n", &cl, &cr);
            //printf("%c %c\n", cl, cr);
            if(cl != '-') {
                T[i].left = cl - '0';
                check[T[i].left] = 1;
            } else {
                T[i].left = -1;
            }
    
            if(cr != '-') {
                T[i].right = cr - '0';
                check[T[i].right] = 1;
            } else {
                T[i].right = -1;
            }   
        }
        for(int i = 0; i < N; i++) {
            if(check[i] == 0) {
                root = i;
                break;
            }
        }
    } else {
        root = -1;
    }
    return root;
}
 
// 层次遍历输出叶子节点 

void levelOrderTraversal(int root){
    if(root == -1) return ; 
    int current;
    queue<int> Q;
    Q.push(root);
    bool flag = true;
    while(!Q.empty()) {
        current = Q.front();
        Q.pop();
        
        if(Tr[current].left == -1 && Tr[current].right == -1) {
            if(flag) {
                printf("%d", current);  
                flag = false;   
            } else {
                printf(" %d", current); 
            }
        }
        
        if(Tr[current].left != -1) Q.push(Tr[current].left);
        if(Tr[current].right != -1) Q.push(Tr[current].right);
    }
}

int main() {
    
    #ifndef ONLINE_JUDGE
    freopen("ListLeaves.txt", "r", stdin);
    #endif
    
    int root = builTree(Tr);
    levelOrderTraversal(root);
    
    return 0;
}

3.Tree Traversals Again

Problem
给出中序遍历的递归实现，求出后序遍历结果。详细描述

Analysys

观察给出示例，递归版中序遍历的入栈操作即前序遍历结果，出栈顺序即中序遍历结果，可以将问题转化为已知先序、中序，构造树求后序。
先序、中序已知，如何构建树呢？首先由前序确定树根为pre[startPre]在中序序列的位置i，然后递归构造做右子树。

Code

import java.io.*;
import java.util.Scanner;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int v) {
        val = v;
    }
}

public class Main {
    public static boolean flag = true;
    public static int MAXSIZE = 31;
    public static int[] pre = new int[MAXSIZE];
    public static int[] in = new int[MAXSIZE];

    public static TreeNode reConstructBinaryTree(int[] pre, int[] in, int length) {
        TreeNode root = reBuildBinTree(pre, 1, length, in, 1, length);
        return root;
    }

    public static TreeNode reBuildBinTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
        if (startPre > endPre || startIn > endIn) {
            return null;
        }

        TreeNode root = new TreeNode(pre[startPre]);

        for (int i = startIn; i <= endIn; i++) {
            if (in[i] == pre[startPre]) {
                root.left = reBuildBinTree(pre, startPre + 1, startPre + i - startIn, in, startIn, i - 1);
                root.right = reBuildBinTree(pre, startPre + 1 + i - startIn, endPre, in, i + 1, endIn);
            }
        }
        return root;
    }

    public static void postOrderTraversal(TreeNode root) {
        if (root != null) {
            postOrderTraversal(root.left);
            postOrderTraversal(root.right);
            if (flag) {
                System.out.printf("%d", root.val);
                flag = false;
            } else {
                System.out.printf(" %d", root.val);
            }
        }
    }

    public static void main(String[] args) throws FileNotFoundException {
        InputStream is = new BufferedInputStream(new FileInputStream("pta.txt"));
        System.setIn(is);
        Scanner sc = new Scanner(System.in);
        Stack<Integer> stack = new Stack<Integer>();
        int N = sc.nextInt();
        sc.nextLine();
        int preIndex = 1;
        int inIndex = 1;
        for (int i = 1; i <= N * 2; i++) {
            String line = sc.nextLine();
            if (line.contains("Push")) {
                Integer node = Integer.parseInt(line.split(" ")[1]);
                stack.push(node);
                pre[preIndex++] = node;
            } else { 
                if (!stack.empty()) {
                    in[inIndex++] = stack.pop();
                } else {
                    break;
                }
            }
        }

        TreeNode root = reConstructBinaryTree(pre, in, N);
        postOrderTraversal(root);
    }
}

Extension
如果已知后序、中序，求前序呢？思路和上题一样。

Code

import java.io.*;
import java.util.Scanner;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int v) {
        val = v;
    }
}

public class Main {
    public static boolean flag = true;

    public static TreeNode reBuildBinTreePostIn(int[] post, int startPost, int endPost, 
        int[] in, int startIn, int endIn) {
        if (startPost > endPost || startIn > endIn) {
            return null;
        }

        TreeNode root = new TreeNode(post[endPost]);
        for (int i = startIn; i <= endIn; i++) {
            if (in[i] == post[endPost]) {
                root.left = reBuildBinTreePostIn(post, startPost, startPost + i - startIn-1, in, startIn, i - 1);
                root.right = reBuildBinTreePostIn(post, endPost - (endIn - i), endPost - 1, in, i + 1, endIn);
            }
        }
        return root;
    }

    public static void preOrderTraversal(TreeNode root) {
        if (root != null) {
            if (flag) {
                System.out.printf("%d", root.val);
                flag = false;
            } else {
                System.out.printf(" %d", root.val);
            }
            preOrderTraversal(root.left);
            preOrderTraversal(root.right);
        }
    }
    
    public static void main(String[] args) throws FileNotFoundException {
        // 读入前序遍历序列
        int[] pre = new int[]{7,4,1,5,6,9,8,10};
        // 读入中序遍历序列
        int[] in = new int[]{1,4,6,5,7,8,9,10};
        // 读入后序遍历序列
        int[] post = new int[]{1,6,5,4,8,10,9,7};

        TreeNode root = reBuildBinTreePostIn(post, 0, 7, in, 0, 7);
        preOrderTraversal(root);
    }
}

声明：本站所有文章均为原创或翻译，遵循署名 - 非商业性使用 - 禁止演绎 4.0 国际许可协议，如需转载请确保您对该协议有足够了解，并附上作者名 (Tsukasa) 及原文地址

Tsukasa の部屋

算法刷题笔记四之二叉树上篇

1.树的同构

2.List Leaves

3.Tree Traversals Again

Tsukasa

「My Homepage」
「About Me」
「My Links」

Web Developer

Shenzhen

算法刷题笔记四之二叉树上篇

1.树的同构

2.List Leaves

3.Tree Traversals Again

Tsukasa

「My Homepage」「About Me」「My Links」

Web Developer

Shenzhen

「My Homepage」
「About Me」
「My Links」