二叉树练习题-c++

说明二叉树的两指针域为lchild 与rchild，算法中p为二叉树的根，lh和rh分别为以p为根的二叉树的左子树和右子树的高,hi为以p为根的二叉树的高，hi最后返回。

输入样例：

[3,9,20,null,null,15,7]

输出样例：

3

#include
#include
#include 
#include 
#include 
using namespace std;

struct TreeNode {
     int val;
     TreeNode *lchild;
     TreeNode *rchild;
     TreeNode(int x) : val(x), lchild(NULL), rchild(NULL) {}
 };

class Solution {
public:
    int maxDepth(TreeNode* p) {
		int lh,rh,hi;
		lh = rh = hi = 0;
        if(p != NULL){
			if(p ->lchild == NULL) lh = 0 ; else lh= maxDepth(p->lchild);
			if(p->rchild == NULL)   rh= 0 ; else rh= maxDepth(p->rchild);
			if (lh > rh) hi = 1+lh; else hi=  1+rh;
		}
		else hi = 0;
		return hi;
    }
};

void trimLeftTrailingSpaces(string &input) {
    input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
        return !isspace(ch);
    }));
}

void trimRightTrailingSpaces(string &input) {
    input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
        return !isspace(ch);
    }).base(), input.end());
}

TreeNode* stringToTreeNode(string input) {
    trimLeftTrailingSpaces(input);
    trimRightTrailingSpaces(input);
    input = input.substr(1, input.length() - 2);
    if (!input.size()) {
        return nullptr;
    }

    string item;
    stringstream ss;
    ss.str(input);

    getline(ss, item, ',');
    TreeNode* root = new TreeNode(stoi(item));
    queue nodeQueue;
    nodeQueue.push(root);

    while (true) {
        TreeNode* node = nodeQueue.front();
        nodeQueue.pop();

        if (!getline(ss, item, ',')) {
            break;
        }

        trimLeftTrailingSpaces(item);
        if (item != "null") {
            int leftNumber = stoi(item);
            node->lchild = new TreeNode(leftNumber);
            nodeQueue.push(node->lchild);
        }

        if (!getline(ss, item, ',')) {
            break;
        }

        trimLeftTrailingSpaces(item);
        if (item != "null") {
            int rightNumber = stoi(item);
            node->rchild = new TreeNode(rightNumber);
            nodeQueue.push(node->rchild);
        }
    }
    return root;
}

int main() {
    string line;
    getline(cin, line);
    TreeNode* root = stringToTreeNode(line);
    int ret = Solution().maxDepth(root);
    string out = to_string(ret);
    cout << out << endl;
    return 0;
}

下面是先序遍历二叉树的非递归子程序，请阅读子程序，充空格使其成为完整的算法

输入样例

[1,null,2,3]

输出样例

1
2
3

#include
#include
#include 
#include 
#include 
using namespace std;

struct TreeNode {
     int val;
     TreeNode *lchild;
     TreeNode *rchild;
     TreeNode(int x) : val(x), lchild(NULL), rchild(NULL) {}
 };

class Solution {
public:
	void example(TreeNode * b){
		TreeNode * stack[20],* p;
		int top;
		if (b != NULL){
			top = 1;
			stack[top] = b;
			while (top > 0){
				p = stack[top] ; top--;
				cout << p -> val << endl;
				if(p -> rchild != NULL){
					top++;
					stack[top] = p->rchild;
				}
				if(p -> lchild != NULL){
					top++;
					stack[top] = p->lchild; 
				}
			}
		}
	}
};

void trimLeftTrailingSpaces(string &input) {
    input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
        return !isspace(ch);
    }));
}

void trimRightTrailingSpaces(string &input) {
    input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
        return !isspace(ch);
    }).base(), input.end());
}

TreeNode* stringToTreeNode(string input) {
    trimLeftTrailingSpaces(input);
    trimRightTrailingSpaces(input);
    input = input.substr(1, input.length() - 2);
    if (!input.size()) {
        return nullptr;
    }

    string item;
    stringstream ss;
    ss.str(input);

    getline(ss, item, ',');
    TreeNode* root = new TreeNode(stoi(item));
    queue nodeQueue;
    nodeQueue.push(root);

    while (true) {
        TreeNode* node = nodeQueue.front();
        nodeQueue.pop();

        if (!getline(ss, item, ',')) {
            break;
        }

        trimLeftTrailingSpaces(item);
        if (item != "null") {
            int leftNumber = stoi(item);
            node->lchild = new TreeNode(leftNumber);
            nodeQueue.push(node->lchild);
        }

        if (!getline(ss, item, ',')) {
            break;
        }

        trimLeftTrailingSpaces(item);
        if (item != "null") {
            int rightNumber = stoi(item);
            node->rchild = new TreeNode(rightNumber);
            nodeQueue.push(node->rchild);
        }
    }
    return root;
}

int main() {
    string line;
    getline(cin, line);
    TreeNode* root = stringToTreeNode(line);
    Solution().example(root);
    return 0;
}

下面是中序线索树的遍历算法，树有头结点且由指针thr 指向。树的结点有五个域,分别为:数据域data，左、右孩子域lchild和 rchild，左、右标志域ltag和 rtag。规定标志域为1是线索,0是指向孩子的指针。

输入案例

[1,2,3]

输出案例

2
1
3

#include
#include
#include 
#include 
#include 
using namespace std;

struct TreeNode {
     int val;
     TreeNode *lchild;
     TreeNode *rchild;
	 int ltag;
	 int rtag;
     TreeNode(int x) : val(x),ltag(0),rtag(0), lchild(NULL), rchild(NULL) {}
 };


class Solution {
public:
	void inorderthread(TreeNode * thr) {
		TreeNode * p = thr;
		while (p != NULL){
			while(!p->ltag) p= p->lchild;
			cout << p-> val << endl;
			while(p->rtag){
				p = p->rchild; 
				cout << p -> val << endl; 
			}
			p = p->rchild;
		}
	}
};




void trimLeftTrailingSpaces(string &input) {
    input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
        return !isspace(ch);
    }));
}

void trimRightTrailingSpaces(string &input) {
    input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
        return !isspace(ch);
    }).base(), input.end());
}


void inThread(TreeNode *p, TreeNode *&pre){
    if(p){
        inThread(p->lchild, pre); //线索化左子树
		if(p->lchild == NULL){
			p->lchild = pre;
			p->ltag = 1;
		}
		if(pre != NULL && pre->rchild == NULL){
			pre->rchild = p;
			pre->rtag = 1;
		}
		pre = p;
		inThread(p->rchild, pre);
    }
}

void createThreadTree(TreeNode * root){
    TreeNode * pre = NULL;
    if(root){
        inThread(root, pre);
    }
}


TreeNode* stringToTreeNode(string input) {
    trimLeftTrailingSpaces(input);
    trimRightTrailingSpaces(input);
    input = input.substr(1, input.length() - 2);
    if (!input.size()) {
        return nullptr;
    }

    string item;
    stringstream ss;
    ss.str(input);

    getline(ss, item, ',');
    TreeNode* root = new TreeNode(stoi(item));
    queue nodeQueue;
    nodeQueue.push(root);

    while (true) {
        TreeNode* node = nodeQueue.front();
        nodeQueue.pop();

        if (!getline(ss, item, ',')) {
            break;
        }

        trimLeftTrailingSpaces(item);
        if (item != "null") {
            int leftNumber = stoi(item);
            node->lchild = new TreeNode(leftNumber);
            nodeQueue.push(node->lchild);
        }

        if (!getline(ss, item, ',')) {
            break;
        }

        trimLeftTrailingSpaces(item);
        if (item != "null") {
            int rightNumber = stoi(item);
            node->rchild = new TreeNode(rightNumber);
            nodeQueue.push(node->rchild);
        }
    }
    return root;
}

int main() {
    string line;
    getline(cin, line);
    TreeNode* root = stringToTreeNode(line);
	createThreadTree(root);
    Solution().inorderthread(root);
    //TravIn_Thread_BT(root);
	return 0;
}