巫山那家做网站,东莞营销网站建设服务,麒麟seo,上海企业网上预登记144. 二叉树的前序遍历
递归写法很简单#xff0c;不再赘述。迭代写法需要用到一个栈#xff0c;因为是根-左子树-右子树的顺序进行遍历#xff0c;所以弹出当前结点后要先入栈右儿子#xff0c;再入栈左儿子。
/*** Definition for a binary tree n…144. 二叉树的前序遍历
递归写法很简单不再赘述。迭代写法需要用到一个栈因为是根-左子树-右子树的顺序进行遍历所以弹出当前结点后要先入栈右儿子再入栈左儿子。
/*** 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:vectorint preorderTraversal(TreeNode* root) {vectorint res;pre(root, res);return res;}void pre(TreeNode* now, vectorint res){if(!now) return;res.push_back(now-val);if(now-left) pre(now-left, res);if(now-right) pre(now-right, res);}
};
//迭代版
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint res;if(root nullptr) return res;stackTreeNode* st;st.push(root);while(st.size()){TreeNode* now st.top();st.pop();res.push_back(now-val);if(now-right) st.push(now-right);if(now-left) st.push(now-left);}return res;}
};
94. 二叉树的中序遍历
递归写法很简单不再赘述。迭代写法也需要一个栈先把根入栈然后每次都看下栈顶结点是否存在左儿子如果有左儿子就把它的左儿子入栈当左儿子不存在的时候需要不断出栈直到刚出栈的这个结点它有右儿子把它的右儿子入栈出栈的顺序就是中序遍历的结果。
/*** 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:vectorint inorderTraversal(TreeNode* root) {vectorint res;if(root nullptr) return res;mid(root, res);return res;}void mid(TreeNode* root, vectorint res){if(root-left) mid(root-left, res);res.push_back(root-val);if(root-right) mid(root-right, res);}
};
//迭代版
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint res;if(root nullptr) return res;stackTreeNode* st;st.push(root);while(st.size()){TreeNode* now st.top();if(now-left) st.push(now-left);else{while(st.size()){TreeNode* top st.top();res.push_back(top-val);st.pop();if(top-right){st.push(top-right);break;}}}}return res;}
};
145. 二叉树的后序遍历
递归写法很简单不再赘述。迭代写法同样也需要一个栈而且思想是和前序遍历一样的可以仿照前序遍历迭代写法然后对结果reverse一下就是后序遍历结果。因为reverse以后要保证是左子树-右子树-根的顺序所以reverse前的顺序就需要是根-右子树-左子树体现在代码上就是前序遍历递归写法中左右儿子入栈顺序交换一下前序遍历中是先入右儿子再入左儿子这里需要先入左儿子再入右儿子。
/*** 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:vectorint postorderTraversal(TreeNode* root) {vectorint res;post(root, res);return res;}void post(TreeNode* root, vectorint res){if(root nullptr) return;post(root-left, res);post(root-right, res);res.push_back(root-val);}
};
//迭代版
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint res;if(root nullptr) return res;stackTreeNode* st;st.push(root);while(st.size()){TreeNode* now st.top();st.pop();res.push_back(now-val);if(now-left) st.push(now-left);if(now-right) st.push(now-right);}reverse(res.begin(), res.end());return res;}
};
102. 二叉树的层序遍历
直接bfs就好了但是网上看到了种dfs的写法也挺新颖的就是递归的时候把所在的层数也作为参数传进去然后每到一个新层开一个空vector存储该层所有结点由于是先序遍历所以同层内还是按照从左向右的顺序存储的。
/*** 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) {}* };*/
//bfs写法
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* q;q.push(root);q.push(nullptr);vectorint nums;vectorvectorint res;if(root nullptr) return res;while(q.size()){TreeNode* now q.front();q.pop();if(!now){res.push_back(nums);if(q.size())q.push(nullptr);nums.clear();}else{nums.push_back(now-val);if(now-left) q.push(now-left);if(now-right) q.push(now-right);}}return res;}
};
662. 二叉树最大宽度
还是一个bfs然后将同层的结点维护在一个vector里不过这里要对结点进行编号可以用二叉树的那种编号方式左儿子和右儿子分别是父节点1和父节点1|1然后维护最大的两编号差值但是这道题最多有3000个结点所以编号很容易溢出同时题目给出了答案不会超出32位int范围也就是说虽然作差的两个编号很大但是差值并不大。所以可以借助模运算只要模一个比int最大值大的数就行了为了方便起见直接用unsigned long long存储所有数据。
/*** 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 widthOfBinaryTree(TreeNode* root) {queuepairTreeNode*, unsigned long long q;q.push(make_pair(root, 1));q.push(make_pair(nullptr, 0));vectorunsigned long long nums;unsigned long long res 0;while(q.size()){TreeNode* now q.front().first;unsigned long long id q.front().second;q.pop();if(id) nums.push_back(id);if(now){if(now-left) q.push(make_pair(now-left, id1));if(now-right) q.push(make_pair(now-right, id1|1));}else{if(q.size()) q.push(make_pair(nullptr, 0));if(nums.size() 1)res max(res, nums[nums.size()-1]-nums[0]1);nums.clear();}}return res;}
};
101. 对称二叉树
这道题主要还是要把握住子结构有两种方法递归或者迭代无论哪种方法思想其实都差不多一棵树关于中轴对称需要它的左右子树关于中轴对称所以这道题就转化为判断两颗树是否关于中轴对称。两棵树是否对称有两个条件首先两个根上的值需要相同其次就是树1的左子树要和树2的右子树对称树1的右子树要和树2的左子树对称。这道题的子结构就出来了递归的话就很好写了。迭代法的话需要一个队列类似bfs的思想不过现在是在两棵树上同时bfs结点都放在一个队列里每次入队出队都是两棵树一起所以两棵树的对应结点会在队列中相邻然后看一下这相邻的两结点值是否相同如果出现了不同那就return false入队的时候树1入左儿子紧接着树2要入右儿子树1入右儿子紧接着树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:bool isSymmetric(TreeNode* root) {return check(root, root);}bool check(TreeNode* tr1, TreeNode* tr2){if(!tr1 !tr2) return true;if(!tr1 || !tr2) return false;return tr1-val tr2-val check(tr1-right, tr2-left) check(tr1-left, tr2-right);}
};
//迭代版
class Solution {
public:bool isSymmetric(TreeNode* root) {queueTreeNode* q;q.push(root-left);q.push(root-right);while(q.size()){TreeNode* tr1 q.front();q.pop();TreeNode* tr2 q.front();q.pop();if(!tr1 !tr2) continue;if(!tr1 || !tr2) return false;if(tr1-val ! tr2-val) return false;q.push(tr1-left);q.push(tr2-right);q.push(tr1-right);q.push(tr2-left);}return true;}
};
104. 二叉树的最大深度
递归求解递归左子树和递归右子树取最大值再1作为返回值。
/*** 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;}
};
110. 平衡二叉树
写一个dfs求一下树的深度然后比较左右子树深度就行了。
/*** 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:bool ans true;bool isBalanced(TreeNode* root) {dfs(root);return ans;}int dfs(TreeNode* root){if(root nullptr) return 0;int h1 dfs(root-left);int h2 dfs(root-right);if(abs(h1-h2) 1) ans false;return max(h1, h2)1;}
};
226. 翻转二叉树
比较简单直接递归swap左右儿子就行了。
/*** 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:TreeNode* invertTree(TreeNode* root) {dfs(root);return root;}void dfs(TreeNode* root){if(root nullptr) return;swap(root-left, root-right);dfs(root-left);dfs(root-right);}
};
572. 另一棵树的子树
对于每个结点都进行check判断它是否和给出的子树相同check的过程也是一个递归。
/*** 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:bool isSubtree(TreeNode* root, TreeNode* subRoot) {if(check(root, subRoot)) return true;if(root nullptr) return false;if(isSubtree(root-left, subRoot)) return true;if(isSubtree(root-right, subRoot)) return true;return false;}bool check(TreeNode* root, TreeNode* subRoot){if(!root !subRoot) return true;if(!root || !subRoot) return false;if(root-val ! subRoot-val) return false;return check(root-left, subRoot-left) check(root-right, subRoot-right);}};
112. 路径总和
dfs一遍就行了用参数维护路径上的加和。
/*** 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:bool res false;bool hasPathSum(TreeNode* root, int targetSum) {if(!root) return false;dfs(root, root-val, targetSum);return res;}void dfs(TreeNode* root, int now, int target){if(res) return;if(now target !root-left !root-right){res true;return;}if(root-left) dfs(root-left, nowroot-left-val, target);if(root-right) dfs(root-right, nowroot-right-val, target);}
};
98. 验证二叉搜索树
三种方法最好写的方法就是看下中序序列是否升序因为一棵树是BST等价于它的中序序列升序。第二种方法是写个dfsdfs返回的是当前子树中最大值和最小值存储在一个pair中然后每个结点都判断一下是否该结点值是否大于左子树中的最大值并且小于右子树中的最小值。第三种方法也是dfs和第二种方法的区别在于第二种方法是站在当前结点的角度根据左右子树情况判断当前结点是否合法第三种方法是站在左右子树的角度由于其祖先结点会施加一系列最值约束判断每个结点是否满足其祖先带来的约束就行了。
/*** 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:bool res true;long long last -0x3f3f3f3f3f3f3f3f;bool isValidBST(TreeNode* root) {if(root nullptr) return false;mid(root);return res;}void mid(TreeNode* root){if(!res) return;if(root-left) mid(root-left);if(last root-val)res false;last root-val;if(root-right) mid(root-right);}
};
//法二
class Solution {
public:bool res true;bool isValidBST(TreeNode* root) {dfs(root);return res;}pairint, int dfs(TreeNode* root){if(!res) return make_pair(0, 0);int mn root-val, mx root-val;if(root-left){pairint, int l dfs(root-left);if(root-val l.second) res false;mn min(mn, l.first);}if(root-right){pairint, int r dfs(root-right); if(root-val r.first) res false;mx max(mx, r.second);}return make_pair(mn, mx);}
};
//法三
class Solution {
public:bool isValidBST(TreeNode* root) {return dfs(root, nullptr, nullptr);}bool dfs(TreeNode* root, TreeNode* min, TreeNode* max) {if(root nullptr) return true;if(min ! nullptr root-val min-val) return false;if(max ! nullptr root-val max-val) return false;return dfs(root-right, root, max) dfs(root-left, min, root);}
};
剑指 Offer 54. 二叉搜索树的第k大节点
因为树是一颗BST所以它的中序序列肯定升序所以可以从中序序列里拿到第k大结点。
/*** 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 tmp, res;int findTargetNode(TreeNode* root, int cnt) {tmp cnt;mid(root);return res;}void mid(TreeNode* root){if(tmp 0) return;if(root-right) mid(root-right);tmp--;if(tmp 0) res root-val;if(root-left) mid(root-left);}
};
230. 二叉搜索树中第K小的元素
和找第k大一样的思路也是从中序序列入手。
/*** 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 tmp, res;int kthSmallest(TreeNode* root, int cnt) {tmp cnt;mid(root);return res;}void mid(TreeNode* root){if(tmp 0) return;if(root-left) mid(root-left);tmp--;if(tmp 0) res root-val;if(root-right) mid(root-right);}
};
450. 删除二叉搜索树中的节点
先dfs找到待删除的结点然后如果它左儿子为空那就把待删除结点替换为右儿子如果右儿子为空就把待删除结点替换为左儿子如果都不为空那可以找到左子树中不断找右儿子找到最靠右的那个结点然后把待删除结点右儿子接到它下面之后令待删除结点的左儿子替代待删除结点总之要保证中序序列仍然有序。
/*** 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:TreeNode* deleteNode(TreeNode* root, int key) {dfs(root, key);return root;}void dfs(TreeNode* now, int key){if(now nullptr) return;if(now-val key) dfs(now-left, key);else if(now-val key) dfs(now-right, key);else{if(!now-left) now now-right;else if(!now-right) now now-left;else{TreeNode* p now-left;while(p-right) p p-right;p-right now-right;now now-left;} }}
};
958. 二叉树的完全性检验
跑一个bfs就行了不过空结点也要入队因为完全二叉树的层序序列一定都是非空结点-......-非空结点-空结点-......-空结点这样的顺序所以在bfs过程中记录上一个访问结点然后看相邻两结点是否会出现空结点-非空结点这样的异常情况。
/*** 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:bool isCompleteTree(TreeNode* root) {if(root nullptr) return false;queueTreeNode* q;q.push(root);TreeNode* last root;while(q.size()){TreeNode* now q.front();q.pop();if(now !last) return false;if(now){q.push(now-left);q.push(now-right);}last now;}return true;}
};
剑指 Offer 26. 树的子结构
类似LeetCode572然后也只需要更改一下check函数中的条件就行了。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool isSubStructure(TreeNode* A, TreeNode* B) {if(A nullptr || B nullptr) return false;if(check(A, B)) return true;if(A nullptr) return false;if(isSubStructure(A-left, B)) return true;if(isSubStructure(A-right, B)) return true;return false;}bool check(TreeNode* root, TreeNode* subRoot){if(!subRoot) return true;if(!root) return false;if(root-val ! subRoot-val) return false;return check(root-left, subRoot-left) check(root-right, subRoot-right);}
};
113.路径总和 II
维护一个全局的vector记录dfs路径上的数字序列然后当路经总和为目标值时添加进结果vector就行了。
/*** 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:vectorint nums;vectorvectorint res;vectorvectorint pathSum(TreeNode* root, int targetSum) {if(root nullptr) return res;nums.push_back(root-val);dfs(root, targetSum, root-val);return res;}void dfs(TreeNode* now, int target, int sum){if(target sum !now-left !now-right) res.push_back(nums);if(now-left){nums.push_back(now-left-val);dfs(now-left, target, sumnow-left-val);nums.pop_back();}if(now-right){nums.push_back(now-right-val);dfs(now-right, target, sumnow-right-val);nums.pop_back();}}
};
103. 二叉树的锯齿形层序遍历
按层次bfs遍历一下就行了同时维护一个flag标记代表是否要对该层反转。
/*** 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:vectorvectorint zigzagLevelOrder(TreeNode* root) {queueTreeNode* q;q.push(root);q.push(nullptr);bool flag false;vectorvectorint ans;if(root nullptr) return ans;vectorint t;while(q.size()){TreeNode* now q.front();q.pop();if(now nullptr){if(q.size())q.push(nullptr);if(flag) reverse(t.begin(), t.end());flag !flag;ans.push_back(t);t.clear();}else{t.push_back(now-val);if(now-left) q.push(now-left);if(now-right) q.push(now-right);}}return ans;}
};
199. 二叉树的右视图
和上一题思路一样也是一个按层次bfs取该层最后一个结点放入结果vector中。
/*** 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:vectorint rightSideView(TreeNode* root) {queueTreeNode* q;q.push(root);q.push(nullptr);vectorint ans;if(root nullptr) return ans;vectorint t;while(q.size()){TreeNode* now q.front();q.pop();if(now nullptr){if(q.size())q.push(nullptr);ans.push_back(t[t.size()-1]);t.clear();}else{t.push_back(now-val);if(now-left) q.push(now-left);if(now-right) q.push(now-right);}}return ans;}
};
124. 二叉树中的最大路径和
类似树的直径可以两遍dfs或者树形dp解决这里由于给的树并非无向图所以两遍dfs不好实现可以用哈希映射指针树形dp来求解。另外这里可以对空间进行一次优化dfs直接返回最大值然后次大值在过程中求出来。
/*** 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:unordered_mapTreeNode*, int dp1;unordered_mapTreeNode*, int dp2;int ans -0x3f3f3f3f;int maxPathSum(TreeNode* root) {dfs(root);return ans;}void dfs(TreeNode* now){if(now-left) dfs(now-left);if(now-right) dfs(now-right);dp1[now] dp2[now] 0;if(now-left){if(now-left-valdp1[now-left] dp1[now]){dp2[now] dp1[now];dp1[now] now-left-valdp1[now-left];}else if(now-left-valdp1[now-left] dp2[now])dp2[now] now-left-valdp1[now-left];}if(now-right){if(now-right-valdp1[now-right] dp1[now]){dp2[now] dp1[now];dp1[now] now-right-valdp1[now-right];}else if(now-right-valdp1[now-right] dp2[now])dp2[now] now-right-valdp1[now-right];}ans max(ans, dp1[now]dp2[now]now-val);}
};
//空间优化版
class Solution {
public:int ans -0x3f3f3f3f;int maxPathSum(TreeNode* root) {dfs(root);return ans;}int dfs(TreeNode* now){vectorint a;if(now-left) a.push_back(dfs(now-left)now-left-val);if(now-right) a.push_back(dfs(now-right)now-right-val);int dp1 0, dp2 0;for(int i 0; i a.size(); i){if(a[i] dp1){dp2 dp1;dp1 a[i];}else if(a[i] dp2) dp2 a[i];}ans max(ans, dp1dp2now-val);return dp1;}
};
543. 二叉树的直径
和上一题类似仍然是用树形dp解决。
/*** 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 ans -0xf3f3f3f3f;int diameterOfBinaryTree(TreeNode* root) {dfs(root);return ans;}int dfs(TreeNode* now){int l 0, r 0;if(now-left) l dfs(now-left)1;if(now-right) r dfs(now-right)1;int dp1 max(l, r), dp2 min(l, r);ans max(ans, dp1dp2);return dp1;}
};
236. 二叉树的最近公共祖先
单次询问不需要用树上倍增暴力求LCA就行了先dfs看下两结点深度然后跳到相同深度以后同步跳。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:unordered_mapTreeNode*, TreeNode* fa;int hp, hq;TreeNode* pp, * qq;TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {pp p, qq q;dfs(root, 1);if(hp hq){swap(hp, hq);swap(p, q);}while(hq ! hp){q fa[q];hq--;}while(p ! q){p fa[p];q fa[q];}return p;}void dfs(TreeNode* now, int level){if(now pp) hp level;if(now qq) hq level;if(now-left){fa[now-left] now;dfs(now-left, level1);}if(now-right){fa[now-right] now;dfs(now-right, level1);}}
};
129. 求根节点到叶节点数字之和
一遍dfs就出来了参数维护路径上的数字。
/*** 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:long long ans;int sumNumbers(TreeNode* root) {dfs(root, root-val);return ans;}void dfs(TreeNode* now, long long num){if(!now-left !now-right) ans num;if(now-left) dfs(now-left, num*10now-left-val);if(now-right) dfs(now-right, num*10now-right-val);}
};
105. 从前序与中序遍历序列构造二叉树
思路比较简单用递归实现就行了。
/*** 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:TreeNode* buildTree(vectorint preorder, vectorint inorder) {if(preorder.size() 0) return nullptr;int val preorder[0];TreeNode* root new TreeNode(val);vectorint lin, rin, lpre, rpre;bool flag false;for(int i 0; i inorder.size(); i){if(inorder[i] val){flag true;continue;} if(!flag) lin.push_back(inorder[i]);else rin.push_back(inorder[i]);}for(int i 1; i preorder.size(); i){if(i lin.size()) lpre.push_back(preorder[i]);else rpre.push_back(preorder[i]);}root-left buildTree(lpre, lin);root-right buildTree(rpre, rin);return root;}
};
297. 二叉树的序列化与反序列化
题目要求将二叉树转为字符串然后再根据该字符串新建一棵相同的树可以考虑bfs在层次遍历的过程中记录下来该树然后反序列化的时候类似的操作也是一个bfs的过程具体怎么设计无所谓保证能够恢复出来就行。这道题有两点要特别注意首先是结点值会包含负值所以字符串和数字转换时要注意一下其次是对于字符串的拼接这点操作不当可能会导致MLE之前习惯了str str abc这样的写法但这种写法会额外创建字符串对象str abc
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Codec {
public:stringstream ss;string stoi(int a){ss.clear();ss.str();string res;ss a;ss res;return res;}// Encodes a tree to a single string.string serialize(TreeNode* root) {if(root NULL) return ;queueTreeNode* q;q.push(root);string res ;while(q.size()){TreeNode* now q.front();q.pop();if(now){q.push(now-left);q.push(now-right);res stoi(now-val)#;}else res N#;}return res;}TreeNode* getNext(int pos, string data){int val 0;bool flag false;while(pos data.length() data[pos] ! #){if(data[pos] N){pos 2;return NULL;}else if(data[pos] -){flag true;pos;}else{val val*10data[pos]-0;pos;}}pos;if(flag) val -val;TreeNode* node new TreeNode(val);return node;}// Decodes your encoded data to tree.TreeNode* deserialize(string data) {if(data ) return NULL;int pos 0;queueTreeNode* q;TreeNode* root getNext(pos, data);q.push(root);while(q.size()){TreeNode* now q.front();q.pop();now-left getNext(pos, data);now-right getNext(pos, data);if(now-left) q.push(now-left);if(now-right) q.push(now-right);}return root;}
};// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans deser.deserialize(ser.serialize(root));
114. 二叉树展开为链表
典型的可以用递归解决的问题对于一棵树先递归处理其左右子树将其左右子树展开为链表dfs返回值应该是展成链表后最后一个结点的指针用两个指针l、r分别记录左右子树末尾节点这样对于当前这棵树now就可以令l-right now-right, now-right now-left, now-left nullptr此时就完成将now树展为链表操作了。
/*** 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 flatten(TreeNode* root) {if(root nullptr) return;dfs(root);}TreeNode* dfs(TreeNode* now){if(now nullptr) return nullptr;TreeNode* l dfs(now-left);TreeNode* r dfs(now-right);if(l !r){now-right now-left;now-left nullptr;return l;}else if(l r){l-right now-right;now-right now-left;now-left nullptr;return r;}else if(!l !r) return now;else return r;}
};
剑指 Offer 36. 二叉搜索树与双向链表
这道题有点类似上一道把二叉树展成链表也是利用递归的思想如果左子树和右子树已经是有序的双向链表那就很好处理了左中右一拼接就行了。
/*
// Definition for a Node.
class Node {
public:int val;Node* left;Node* right;Node() {}Node(int _val) {val _val;left NULL;right NULL;}Node(int _val, Node* _left, Node* _right) {val _val;left _left;right _right;}
};
*/
class Solution {
public:Node* treeToDoublyList(Node* root) {return dfs(root).first;}pairNode*, Node* dfs(Node* now){if(now NULL) return make_pair((Node*)NULL, (Node*)NULL);pairNode*, Node* l dfs(now-left);pairNode*, Node* r dfs(now-right);Node* ls l.first, * le l.second;Node* rs r.first, * re r.second;if(!ls !rs){now-left now;now-right now;return make_pair(now, now);}else if(!ls rs){rs-left now;re-right now;now-right rs;now-left re;return make_pair(now, re);}else if(ls !rs){ls-left now;le-right now;now-left le;now-right ls;return make_pair(ls, now);}else{now-left le;now-right rs;le-right now;rs-left now;ls-left re;re-right ls;return make_pair(ls, re);}}
};
