二叉树的遍历：
前序遍历： 根左右
中序遍历：左根右
后序遍历： 左右根
计算二叉树有多少个结点
int count(TreeNode root){ if(root==null) return 0; return 1 + count(root.left)+count(root.right); }226. 翻转二叉树
难度简单645收藏分享切换为英文接收动态反馈
翻转一棵二叉树。
示例：
输入：
4 / \ 2 7 / \ / \ 1 3 6 9输出：
4 / \ 7 2 / \ / \ 9 6 3 1备注: 这个问题是受到 Max Howell 的 原问题 启发的 ：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。 /** * 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: TreeNode* invertTree(TreeNode* root) { //base case 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. 填充每个节点的下一个右侧节点指针
难度中等258收藏分享切换为英文接收动态反馈
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node { int val; Node *left; Node *right; Node *next; }填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例：
输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1} 输出：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1} 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。 /* // 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; connectTwoNode(root->left,root->right); return root; } //定义： 输入两个节点，将其链接起来 void connectTwoNode(Node* node1,Node* node2) { if(node1==NULL || node2==NULL) return; // 左右根 node1->next = node2; //；链接相同父节点的两个节点 connectTwoNode(node1->left,node1->right); connectTwoNode(node2->left,node2->right); connectTwoNode(node1->right,node2->left); } };114. 二叉树展开为链表
难度中等572收藏分享切换为英文接收动态反馈
给定一个二叉树，原地将它展开为一个单链表。
例如，给定二叉树
1 / \ 2 5 / \ \ 3 4 6将其展开为：
1 \ 2 \ 3 \ 4 \ 5 \ 6通过次数85,514提交次数120,197
/** * 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) { //base case if (root==nullptr) return; flatten(root->left); flatten(root->right); //后序遍历 //1/ 左右子树已经被拉为一条链表 TreeNode* left = root->left; TreeNode* right = root->right; //2.将左子树变为右子树 root->left = nullptr; root->right = left; //3. 将原来的右子树接到当前右子树末端 TreeNode* p = root; while(p->right !=nullptr) { p = p->right; } p->right = right; } };参考链接：https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247487126&idx=1&sn=4de13e66397bc35970963c5a1330ce18&chksm=9bd7f09eaca0798853c41fba05ad5fa958b31054eba18b69c785ae92f4bd8e4cc7a2179d7838&token=147394321&lang=zh_CN#rd
