leetcode116：填充每个节点的下一个右侧节点指针
-
题目：给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
-
思路：采用遍历的方式，将二叉树看作为三叉树进行遍历；
-
同一层且相同父节点的子左右节点，左节点指向右节点；
-
同一层且不同父节点的相邻节点，将左子节点的右节点指向右子节点的左节点。
class Solution {
? ?public Node connect(Node root) {
? ? ? ?if(root==null){
? ? ? ? ? ?return null;
? ? ? }
? ? ? ?traverse(root.left,root.right);
?
? ? ? ?return root;
?
? ? ? ?
? }
?
? ?void traverse(Node node1,Node node2){
? ? ? ?if(node1==null||node2==null){
? ? ? ? ? ?return;
? ? ? }
? ? ? ?//将同一层的相邻两个节点相连
? ? ? ?node1.next = node2;
?
? ? ? ?//同一层且相同父节点的子左右节点
? ? ? ?traverse(node1.left,node1.right);
? ? ? ?traverse(node2.left,node2.right);
? ? ? ?//同一层且不同父节点的相邻节点
? ? ? ?traverse(node1.right,node2.left);
?
? }
}
leetcode114.二叉树展开为链表
-
题目：给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。 展开后的单链表应该与二叉树 先序遍历 顺序相同。
-
思路：采用递归的方式，将根节点的子右节点连接到根节点的子左节点，依据此继续递归到其子节点。
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 p = root;
? ? ? ?while(p.right!=null){
? ? ? ? ? ?p = p.right;
? ? ? }
? ? ? ?p.right = right;
? }
}
