毕节市建设厅网站,百度获客平台怎么收费的,建设中专网站,招聘网站建设需求分析题目
给定一个二叉树的根节点 root #xff0c;返回 它的 中序 遍历 。
示例 示例 1#xff1a; 输入#xff1a;root [1,null,2,3]
输出#xff1a;[1,3,2]示例 2#xff1a; 输入#xff1a;root []
输出#xff1a;[]示例 3#xff1a; 输入#xff1a;root […题目
给定一个二叉树的根节点 root 返回 它的 中序 遍历 。
示例 示例 1 输入root [1,null,2,3]
输出[1,3,2]示例 2 输入root []
输出[]示例 3 输入root [1]
输出[1] 分析
二叉树的中序遍历顺序是先遍历左子树然后访问根节点最后遍历右子树。
递归法
递归是实现二叉树中序遍历最简单的方法其基本思想是根据中序遍历的定义递归地处理左子树、根节点和右子树。
时间复杂度O() 为二叉树节点的个数
空间复杂度O()递归调用栈的空间最坏情况下二叉树退化为链表递归深度为
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint result;inorder(root, result);return result;}
private:void inorder(TreeNode* node, vectorint result) {if (node nullptr) {return;}// 递归遍历左子树inorder(node-left, result);// 访问根节点result.push_back(node-val);// 递归遍历右子树inorder(node-right, result);}
};
迭代法
迭代实现通常使用栈来模拟递归调用的过程。具体步骤如下
从根节点开始将左子树的节点依次压入栈中直到左子树为空弹出栈顶节点访问该节点的值处理该节点的右子树重复步骤 1 和 2
时间复杂度O() 为二叉树节点的个数
空间复杂度O()递归调用栈的空间最坏情况下二叉树退化为链表递归深度为
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* nodeStack;TreeNode* current root;while (current ! nullptr || !nodeStack.empty()) {// 将左子树的节点依次压入栈中while (current ! nullptr) {nodeStack.push(current);current current-left;}// 弹出栈顶节点并访问current nodeStack.top();nodeStack.pop();result.push_back(current-val);// 处理右子树current current-right;}return result;}
};
知识充电
二叉树性质
若规定根节点的层数为 1则一棵非空二叉树的第 i 层上最多有 个节点
若规定根节点的层数为 1则深度为 h 的二叉树的最大节点数是
对任何一棵二叉树如果其叶节点个数为 度为 2 的非叶节点个数为 则有
常见操作
初始化
#include iostream
#include vector
#include stack// 二叉树节点定义
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
插入节点
// 插入节点以二叉搜索树为例
TreeNode* insertNode(TreeNode* root, int val) {if (root nullptr) {return new TreeNode(val);}if (val root-val) {root-left insertNode(root-left, val);} else {root-right insertNode(root-right, val);}return root;
}
int main() {TreeNode* root nullptr;root insertNode(root, 50);insertNode(root, 30);insertNode(root, 20);insertNode(root, 40);insertNode(root, 70);insertNode(root, 60);insertNode(root, 80);return 0;
}
查找节点
// 查找节点以二叉搜索树为例
TreeNode* searchNode(TreeNode* root, int val) {if (root nullptr || root-val val) {return root;}if (val root-val) {return searchNode(root-left, val);} else {return searchNode(root-right, val);}
}
// 辅助函数插入节点
TreeNode* insertNode(TreeNode* root, int val) {if (root nullptr) {return new TreeNode(val);}if (val root-val) {root-left insertNode(root-left, val);} else {root-right insertNode(root-right, val);}return root;
}
int main() {TreeNode* root nullptr;root insertNode(root, 50);insertNode(root, 30);insertNode(root, 20);insertNode(root, 40);insertNode(root, 70);insertNode(root, 60);insertNode(root, 80);TreeNode* found searchNode(root, 40);if (found) {std::cout Found node with value: found-val std::endl;} else {std::cout Node not found. std::endl;}return 0;
}
删除节点
// 找到右子树中的最小节点
TreeNode* findMin(TreeNode* node) {while (node-left ! nullptr) {node node-left;}return node;
}
// 删除节点以二叉搜索树为例
TreeNode* deleteNode(TreeNode* root, int val) {if (root nullptr) {return root;}if (val root-val) {root-left deleteNode(root-left, val);} else if (val root-val) {root-right deleteNode(root-right, val);} else {// 情况 1: 没有子节点或只有一个子节点if (root-left nullptr) {TreeNode* temp root-right;delete root;return temp;} else if (root-right nullptr) {TreeNode* temp root-left;delete root;return temp;}// 情况 2: 有两个子节点TreeNode* temp findMin(root-right);root-val temp-val;root-right deleteNode(root-right, temp-val);}return root;
}
// 辅助函数插入节点
TreeNode* insertNode(TreeNode* root, int val) {if (root nullptr) {return new TreeNode(val);}if (val root-val) {root-left insertNode(root-left, val);} else {root-right insertNode(root-right, val);}return root;
}
int main() {TreeNode* root nullptr;root insertNode(root, 50);insertNode(root, 30);insertNode(root, 20);insertNode(root, 40);insertNode(root, 70);insertNode(root, 60);insertNode(root, 80);root deleteNode(root, 30);return 0;
}
前序遍历
// 前序遍历递归
std::vectorint preorderTraversalRecursive(TreeNode* root) {std::vectorint result;if (root nullptr) return result;result.push_back(root-val);auto leftResult preorderTraversalRecursive(root-left);result.insert(result.end(), leftResult.begin(), leftResult.end());auto rightResult preorderTraversalRecursive(root-right);result.insert(result.end(), rightResult.begin(), rightResult.end());return result;
}
int main() {TreeNode* root new TreeNode(1);root-right new TreeNode(2);root-right-left new TreeNode(3);std::vectorint preorderRecursive preorderTraversalRecursive(root);return 0;
}
中序遍历
// 中序遍历递归
std::vectorint inorderTraversalRecursive(TreeNode* root) {std::vectorint result;if (root nullptr) return result;auto leftResult inorderTraversalRecursive(root-left);result.insert(result.end(), leftResult.begin(), leftResult.end());result.push_back(root-val);auto rightResult inorderTraversalRecursive(root-right);result.insert(result.end(), rightResult.begin(), rightResult.end());return result;
}
int main() {TreeNode* root new TreeNode(1);root-right new TreeNode(2);root-right-left new TreeNode(3);std::vectorint inorderRecursive inorderTraversalRecursive(root);return 0;
}
后序遍历
// 后序遍历递归
std::vectorint postorderTraversalRecursive(TreeNode* root) {std::vectorint result;if (root nullptr) return result;auto leftResult postorderTraversalRecursive(root-left);result.insert(result.end(), leftResult.begin(), leftResult.end());auto rightResult postorderTraversalRecursive(root-right);result.insert(result.end(), rightResult.begin(), rightResult.end());result.push_back(root-val);return result;
}
int main() {TreeNode* root new TreeNode(1);root-right new TreeNode(2);root-right-left new TreeNode(3);std::vectorint postorderRecursive postorderTraversalRecursive(root);return 0;
}
