/* * @lc app=leetcode.cn id=226 lang=cpp * * [226] 翻转二叉树 * * https://leetcode-cn.com/problems/invert-binary-tree/description/ * * algorithms * Easy (78.27%) * Likes: 875 * Dislikes: 0 * Total Accepted: 243.6K * Total Submissions: 310.5K * Testcase Example: '[4,2,7,1,3,6,9]' * * 翻转一棵二叉树。 * * 示例： * * 输入： * * 4 * / * 2 7 * / / * 1 3 6 9 * * 输出： * * 4 * / * 7 2 * / / * 9 6 3 1 * * 备注: * 这个问题是受到 Max Howell 的 原问题 启发的 ： * * 谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。 * */ // @lc code=start /** * 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) { if(root==NULL) return NULL; TreeNode* tmp=root->left; root->left=root->right; root->right=tmp; invertTree(root->left); invertTree(root->right); return root; } };
116
/* * @lc app=leetcode.cn id=116 lang=cpp * * [116] 填充每个节点的下一个右侧节点指针 * * https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/description/ * * algorithms * Medium (69.34%) * Likes: 469 * Dislikes: 0 * Total Accepted: 121.4K * Total Submissions: 174.4K * Testcase Example: '[1,2,3,4,5,6,7]' * * 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下： * * * struct Node { * int val; * Node *left; * Node *right; * Node *next; * } * * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。 * * 初始状态下，所有 next 指针都被设置为 NULL。 * * * * 进阶： * * * 你只能使用常量级额外空间。 * 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。 * * * * * 示例： * * * * * 输入：root = [1,2,3,4,5,6,7] * 输出：[1,#,2,3,#,4,5,6,7,#] * 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B * 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。 * * * * * 提示： * * * 树中节点的数量少于 4096 * -1000 * * */ // @lc code=start /* // Definition for a Node. class Node { public: int val; Node* left; Node* right; Node* next; Node() : val(0), left(NULL), right(NULL), next(NULL) {} Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {} Node(int _val, Node* _left, Node* _right, Node* _next) : val(_val), left(_left), right(_right), next(_next) {} }; */
思路：
二叉树的问题难点在于，如何把题目的要求细化成每个节点需要做的事情，但是如果只依赖一个节点的话，肯定是没办法连接「跨父节点」的两个相邻节点的。
那么，我们的做法就是增加函数参数，一个节点做不到，我们就给他安排两个节点，「将每一层二叉树节点连接起来」可以细化成「将每两个相邻节点都连接起来」
class Solution { public: Node* connect(Node* root) { if(root==NULL) return NULL; connect2(root->left, root->right); return root; } void connect2(Node* left, Node* right){ if(left==NULL||right==NULL) return; left->next=right; connect2(left->left, left->right); connect2(right->left, right->right); connect2(left->right, right->left); } };
[114] 二叉树展开为链表
/* * @lc app=leetcode.cn id=114 lang=cpp * * [114] 二叉树展开为链表 * * https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/description/ * * algorithms * Medium (72.11%) * Likes: 816 * Dislikes: 0 * Total Accepted: 141.5K * Total Submissions: 195.6K * Testcase Example: '[1,2,5,3,4,null,6]' * * 给你二叉树的根结点 root ，请你将它展开为一个单链表： * * * 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。 * 展开后的单链表应该与二叉树 先序遍历 顺序相同。 * * * * * 示例 1： * * * 输入：root = [1,2,5,3,4,null,6] * 输出：[1,null,2,null,3,null,4,null,5,null,6] * * * 示例 2： * * * 输入：root = [] * 输出：[] * * * 示例 3： * * * 输入：root = [0] * 输出：[0] * * * * * 提示： * * * 树中结点数在范围 [0, 2000] 内 * -100 * * * * * 进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？ * */ // @lc code=start /** * 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) {} * }; */
思路：
1、将root的左子树和右子树拉平。
2、将root的右子树接到左子树下方，然后将整个左子树作为右子树。
class Solution { public: void flatten(TreeNode* root) { if(root==NULL) return; flatten(root->left); flatten(root->right); TreeNode* left=root->left; TreeNode* right=root->right; root->left=NULL; root->right=left; TreeNode* tmp=root; while(tmp->right!=NULL) tmp=tmp->right; tmp->right=right; } };