在一棵二叉链表表示的二叉树中，实现以下操作，并分别采用先根、中根、后根遍历算法。 ① 输入叶子结点。 ② 求二叉树中叶子结点个数。 ③ 将每个结点的左子树与右子树交换。 ④ 验证二叉树的性质3：n0=n2+1。 ⑤ 输出值大于k的结点。 ⑥ 已知先根和中根次序遍历序列构造二叉树。 ⑦ 以广义表表示构造二叉树。 ⑧ 判断两颗二叉树是否相等。 ⑨ 求结点所在的层次。 ⑩ 求一颗二叉树在后根次序遍历下第一个访问的结点。 ⑪ 复制一颗二叉树。 ⑫ 判断一颗二叉树是否为完全二叉树。 ⑬ 实现二叉树后根次序遍历的非递归算法。

好的，我会根据您的问题进行回答。以下是每个问题的回答： ① 输入叶子结点：由于二叉树的叶子结点是没有子结点的，因此可以直接输入该结点的值，然后将其设为叶子结点。 ② 求二叉树中叶子结点个数：可以采用递归的方式，对于每个结点，如果它没有左右子结点，则它是叶子结点，将叶子结点个数加1；否则分别递归遍历它的左右子树，将左右子树中的叶子结点个数相加即可。 ③ 将每个结点的左子树与右子树交换：可以采用递归的方式，对于每个结点，交换它的左右子树即可。具体实现可以参考以下代码： ```c++ void swap(TreeNode* root) { if (root == NULL) { return; } TreeNode* tmp = root->left; root->left = root->right; root->right = tmp; swap(root->left); swap(root->right); } ``` ④ 验证二叉树的性质3：n0=n2+1。n0表示度数为0的结点个数，n2表示度数为2的结点个数。可以采用递归的方式，对于每个结点，统计它的度数，最后判断是否满足n0=n2+1的关系即可。 ```c++ bool check(TreeNode* root) { if (root == NULL) { return true; } int n0 = 0, n2 = 0; if (root->left == NULL && root->right == NULL) { n0++; } else if (root->left != NULL && root->right != NULL) { n2++; } else { return false; } n0 += check(root->left) + check(root->right); n2 += check(root->left) + check(root->right); return n0 == n2 + 1; } ``` ⑤ 输出值大于k的结点：可以采用递归的方式，对于每个结点，如果它的值大于k，则输出该结点的值，然后递归遍历它的左右子树，查找值大于k的结点。 ```c++ void print(TreeNode* root, int k) { if (root == NULL) { return; } if (root->val > k) { cout << root->val << " "; } print(root->left, k); print(root->right, k); } ``` ⑥ 已知先根和中根次序遍历序列构造二叉树：可以采用递归的方式，先根遍历序列的第一个结点一定是根结点，然后在中根遍历序列中找到根结点的位置，它左边的结点是左子树的中根遍历序列，右边的结点是右子树的中根遍历序列。然后递归构造左右子树即可。 ```c++ TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pre_start, int pre_end, int in_start, int in_end) { if (pre_start > pre_end || in_start > in_end) { return NULL; } TreeNode* root = new TreeNode(preorder[pre_start]); int root_pos = in_start; while (root_pos <= in_end && inorder[root_pos] != root->val) { root_pos++; } int left_size = root_pos - in_start; root->left = build(preorder, inorder, pre_start + 1, pre_start + left_size, in_start, root_pos - 1); root->right = build(preorder, inorder, pre_start + left_size + 1, pre_end, root_pos + 1, in_end); return root; } ``` ⑦ 以广义表表示构造二叉树：可以采用递归的方式，对于每个结点，先读入它的值，然后判断下一个字符是不是左括号，如果是，则递归构造它的左子树和右子树，否则返回NULL。 ```c++ TreeNode* build(string& s, int& pos) { if (s[pos] == '(') { pos++; int val = 0; bool negative = false; if (s[pos] == '-') { negative = true; pos++; } while (isdigit(s[pos])) { val = val * 10 + s[pos] - '0'; pos++; } if (negative) { val = -val; } TreeNode* root = new TreeNode(val); root->left = build(s, pos); root->right = build(s, pos); pos++; return root; } return NULL; } ``` ⑧ 判断两颗二叉树是否相等：可以采用递归的方式，对于每个结点，分别判断它的值、左子树和右子树是否相等即可。 ```c++ bool isSame(TreeNode* root1, TreeNode* root2) { if (root1 == NULL && root2 == NULL) { return true; } if (root1 == NULL || root2 == NULL) { return false; } return root1->val == root2->val && isSame(root1->left, root2->left) && isSame(root1->right, root2->right); } ``` ⑨ 求结点所在的层次：可以采用递归的方式，对于每个结点，如果它是根结点，则它所在的层次是1；否则它的层次等于它的父结点的层次加1。 ```c++ int getLevel(TreeNode* root, TreeNode* node, int level) { if (root == NULL) { return 0; } if (root == node) { return level; } int left_level = getLevel(root->left, node, level + 1); if (left_level != 0) { return left_level; } return getLevel(root->right, node, level + 1); } ``` ⑩ 求一颗二叉树在后根次序遍历下第一个访问的结点：可以采用递归的方式，对于每个结点，先递归遍历它的左右子树，然后访问它本身。最后返回访问的第一个结点。 ```c++ TreeNode* getLastVisit(TreeNode* root) { if (root == NULL) { return NULL; } TreeNode* last_left = getLastVisit(root->left); TreeNode* last_right = getLastVisit(root->right); if (last_left != NULL) { return last_left; } if (last_right != NULL) { return last_right; } return root; } ``` ⑪ 复制一颗二叉树：可以采用递归的方式，对于每个结点，先复制它本身，然后递归复制它的左右子树。 ```c++ TreeNode* copy(TreeNode* root) { if (root == NULL) { return NULL; } TreeNode* new_root = new TreeNode(root->val); new_root->left = copy(root->left); new_root->right = copy(root->right); return new_root; } ``` ⑫ 判断一颗二叉树是否为完全二叉树：可以采用递归的方式，对于每个结点，如果它是叶子结点，则它的左右子树都应该是空，否则它的左右子树中至少有一个不为空，且它的左子树应该是满二叉树，右子树可能是满二叉树或者完全二叉树。 ```c++ bool isComplete(TreeNode* root, int depth, int level) { if (root == NULL) { return true; } if (root->left == NULL && root->right == NULL) { return depth == level; } if (root->left != NULL && root->right != NULL) { return isComplete(root->left, depth, level + 1) && isComplete(root->right, depth, level + 1); } if (root->left != NULL) { return false; } return isComplete(root->right, depth, level + 1) && level == depth - 1; } bool isComplete(TreeNode* root) { int depth = getDepth(root); return isComplete(root, depth, 1); } ``` ⑬ 实现二叉树后根次序遍历的非递归算法：可以采用栈来模拟后根次序遍历的过程。对于每个结点，先将它的左右子树入栈，然后依次访问栈顶元素，直到栈为空。 ```c++ vector<int> postorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> s; s.push(root); while (!s.empty()) { TreeNode* cur = s.top(); s.pop(); if (cur == NULL) { continue; } s.push(cur->left); s.push(cur->right); res.insert(res.begin(), cur->val); } return res; } ```