力扣226题,116题,114题（二叉树、递归）还没搞懂 226.翻转二叉树 116.填充二叉树结点的右侧指针 114、将二叉树展开为链表
基本思想：
把二叉树上的每一个节点的左右子节点进行交换，最后的结果就是完全翻转之后的二叉树。
具体实现：
1.递归的参数和返回值
参数：根节点
返回值：无
2.递归结束条件
当前节点为空时返回
3.单层递归逻辑
前序遍历 先交换再递归
（1）使用前序遍历，交换某一个节点的左右子节点
（2）左右子节点再翻转它们的子节点
后序遍历 先递归再交换
代码：
class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } swapChildren(root);//前序遍历 invertTree(root.left); invertTree(root.right); //swapChildren(root); //后序遍历 return root; } private void swapChildren(TreeNode root){ TreeNode tmp = root.left; root.left = root.right; root.right = tmp; } }
层序遍历
class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } ArrayDeque<TreeNode> deque = new ArrayDeque<>(); deque.offer(root); while (!deque.isEmpty()) { int size = deque.size(); while (size-- >0 ){ TreeNode node = deque.poll(); swapChildren(node); if (node.left != null) { deque.offer(node.left); } if (node.right != null) { deque.offer(node.right); } } } return root; } private void swapChildren(TreeNode root){ TreeNode tmp = root.left; root.left = root.right; root.right = tmp; } }
116.填充二叉树结点的右侧指针
基本思想：
增加函数参数，将每一层二叉树节点连接起来转化为将每两个相邻节点连接起来
具体实现：
1、基本操作是将相邻两节点连接起来
root_a.next = root_b
2、相邻节点分为三种情况
连接相同父节点的两个子节点
（1）root_a.left.next = root_a.right
（2）root_b.left.next = root_b.right
跨越父节点的两个子节点
（3）root_a.right.next = root_b.lef
代码：
114、将二叉树展开为链表
基本思想：
先拉平左右子树，再将左右子树拼接。
递归框架是后序遍历，因为需要先拉平左右子树，再进行后续操作。
具体实现：
1.求解子问题，把只有三个节点的树进行转换
（1）root.left.right = root.right
(2)root.right = root.left
(3)root.left = None
2.root的左结点和右结点都转换好了，需要把左右节点拼起来
（1）设置一个游标通过循环找到左节点的末尾
index = root.left while index.right: index = index.right
(2)将root右结点拼到左结点的末尾上
index.right = root.right
(3)把root左结点放到右结点上
root.right = root.left
(4)root左结点为空