北京城市建设档案馆网站,wordpress 搜索词,首都博物馆 网站建设,互联网营销师有必要考吗目录
1 基础知识
1.1 先序遍历
1.2 中序遍历
1.3 后序遍历
2 94. 二叉树的中序遍历
3 104. 二叉树的最大深度
4 226. 翻转二叉树
5 101. 对称二叉树 菜鸟做题#xff0c;语言是 C 1 基础知识
二叉树常见的遍历方式有#xff1a;
先序遍历中序遍历后序遍历…目录
1 基础知识
1.1 先序遍历
1.2 中序遍历
1.3 后序遍历
2 94. 二叉树的中序遍历
3 104. 二叉树的最大深度
4 226. 翻转二叉树
5 101. 对称二叉树 菜鸟做题语言是 C 1 基础知识
二叉树常见的遍历方式有
先序遍历中序遍历后序遍历深度优先遍历 先序遍历广度优先遍历 层次遍历后面有道题 其实稍微观察一下就可以发现“先序”、“中序”、“后序” 针对的是根节点的位置。即在 (根节点左子树右子树) 这个三元组中根节点处于哪个位置。 1.1 先序遍历
根节点根节点的左子树根节点的右子树
vectorint ans;
void preorder(TreeNode* root) {if (!root) return;ans.push_back(root-val);preorder(root-left);preorder(root-right);
} 这个例子包括后面的两个例子都是按照指定顺序遍历二叉树同时将每个节点的值放入到容器 ans 中。 1.2 中序遍历
根节点的左子树根节点根节点的右子树
vectorint ans;
void inorder(TreeNode* root) {if (!root) return;inorder(root-left);ans.push_back(root-val);inorder(root-right);
} 1.3 后序遍历
根节点的左子树根节点的右子树根节点
vectorint ans;
void postorder(TreeNode* root) {if (!root) return;postorder(root-left);postorder(root-right);ans.push_back(root-val);
} 2 94. 二叉树的中序遍历
属于中序遍历显然
通过第 1 节的介绍想必解决这个问题就很容易了。需要注意的是我们的递归可以不需要返回值因此需要额外写一个返回值为 void 的函数但貌似你每次都返回一个 vectorint 也行得通
class Solution {
public:void inorder(TreeNode* root, vectorint ans) {if (!root) return;inorder(root-left, ans);ans.push_back(root-val);inorder(root-right, ans);}vectorint inorderTraversal(TreeNode* root) {vectorint ans;inorder(root, ans);return ans;}
}; 3 104. 二叉树的最大深度
属于后序遍历先获得左右子树的最大深度再获得本子树的最大深度
class Solution {
public:int maxDepth(TreeNode* root) {if (!root) return 0;int leftMaxDepth maxDepth(root-left);int rightMaxDepth maxDepth(root-right);return 1 max(leftMaxDepth, rightMaxDepth);}
};
精简版
class Solution {
public:int maxDepth(TreeNode* root) {if (!root) return 0;return 1 max(maxDepth(root-left), maxDepth(root-right));}
}; 4 226. 翻转二叉树
属于先序遍历
解题思路
完成当前节点的翻转完成其左右子树的翻转
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (!root) return nullptr;TreeNode * temp root-right;root-right root-left;root-left temp;invertTree(root-left);invertTree(root-right);return root;}
}; 这道题就没有单独写一个返回值为 void 的函数虽然递归期间的返回值都没有派上用场但是最重要的是最后一个返回值它返回的是整棵二叉树的根节点符合本题对返回值的要求。 5 101. 对称二叉树
属于先序遍历少有的参数需要传两个指针的题
解题思路
判断左右对称位置上的两个节点是否都存在判断这两个节点的值是否相等判断这两个节点的左右子树是否对称
思路说明图 对称位置上的两个节点进行比较即左侧的 “2” 和右侧的 “2”左侧的 “2” 的左子树和右侧的 “2” 的右子树进行比较左侧的 “2” 的右子树和右侧的 “2” 的左子树进行比较
class Solution {
public:bool check(TreeNode * p, TreeNode * q) {if (!p !q) return true;if (!p || !q) return false;return p-val q-val check(p-left, q-right) check(p-right, q-left);}bool isSymmetric(TreeNode* root) {return check(root-left, root-right);}
};
说明
if (!p !q) return true;
if (!p || !q) return false;
第一行判断是指当 p 和 q 都为空指针时属于是对称的情况第二行判断是指当 p 和 q 中只有一方为空指针时属于是非对称的情况。
