144. 二叉树的前序遍历
描述：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
解题思路：
1）若树为空，直接返回 NULL。
2）访问根结点，存下结点的值。
3）递归左子树。
4）递归右子树。
参考代码：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: void preorder(TreeNode *root, vector<int> &ans) { //前序遍历 if (root == nullptr) return; //判断是否为空 ans.push_back(root -> val); preorder(root -> left, ans); //递归左子树 preorder(root -> right, ans); //递归右子树 return; } vector<int> preorderTraversal(TreeNode* root) { vector<int> ans; //结果数组 preorder(root, ans); //前序遍历 return ans; //返回 } };
94. 二叉树的中序遍历
描述：给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
解题思路：
1）若树为空，直接返回 NULL。
2）递归左子树。
3）访问根结点，存下结点的值。
4）递归右子树。
参考代码：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: void inorder(TreeNode* root, vector<int>& ans) {//中序遍历 if (!root) return; //判断是否为空 inorder(root->left, ans); //递归左子树 ans.push_back(root->val); inorder(root->right, ans); //递归右子树 } vector<int> inorderTraversal(TreeNode* root) { vector<int> ans; //结果数组 inorder(root, ans); //中序遍历 return ans; //返回 } };
145. 二叉树的后序遍历
描述：给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
解题思路：
1）若树为空，直接返回 NULL。
2）递归左子树。
3）递归右子树。
4）访问根结点，存下结点的值。
参考代码：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: void postorder(TreeNode *root, vector<int> &ans) {//后序遍历 if (root == nullptr) return; //判断是否为空 postorder(root->left, ans); //遍历左子树 postorder(root->right, ans); //遍历右子树 ans.push_back(root->val); } vector<int> postorderTraversal(TreeNode *root) { vector<int> ans; //答案数组 postorder(root, ans); //后序遍历 return ans; //返回 } };
102. 二叉树的层序遍历
描述：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
解题思路：
1）若树非空，创建辅助队列，头结点入队。
2）将队头结点储存下来记作结点 node，记录结点数据，然后进行出队操作。
3）将结点 node 的左右孩子进行入队操作。
4）重复操作至队列为空。
参考代码：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> que; if (root != NULL) que.push(root); vector<vector<int>> ans; while (!que.empty()) { int size = que.size(); vector<int> vec; for (int i = 0; i < size; i++) { TreeNode* node = que.front(); que.pop(); vec.push_back(node->val); if (node->left) que.push(node->left); if (node->right) que.push(node->right); } ans.push_back(vec); } return ans; } };
104. 二叉树的最大深度
描述：
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
解题思路：
1）当遇到空结点时，返回 0。
2）递归计算出其左子树和右子树的最大深度。
参考代码：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int maxDepth(TreeNode* root) { if (root == nullptr) return 0; return max(maxDepth(root->left), maxDepth(root->right)) + 1; } };
