力扣labuladong——一刷day31

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

二叉树解题的思维模式分两类： 1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。 2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。 无论使用哪种思维模式，你都需要思考： 如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。

前言

---

一、力扣226. 翻转二叉树

遍历思想

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode invertTree(TreeNode root) {treaverse(root);return root;}public void treaverse(TreeNode root){if(root == null){return;}TreeNode l = root.left;root.left = root.right;root.right = l;treaverse(root.left);treaverse(root.right);}
}

分解思想

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode invertTree(TreeNode root) {return fun(root);}public TreeNode fun(TreeNode root){if(root == null){return null;}TreeNode lchild = fun(root.left);TreeNode rchild = fun(root.right);root.left = rchild;root.right = lchild;return root;}
}

二、力扣116. 填充每个节点的下一个右侧节点指针

/*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val = _val;}public 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 root;}if(root.left != null && root.right != null){fun(root.left, root.right);}return root;}public void fun(Node node1, Node node2){if(node1 == null || node2 == null){return ;}node1.next = node2;fun(node1.left, node1.right);fun(node2.left,node2.right);fun(node1.right,node2.left);}
}

三、力扣114. 二叉树展开为链表

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public void flatten(TreeNode root) {fun(root);}public TreeNode fun(TreeNode root){if(root == null){return null;}TreeNode r1 = fun(root.left);TreeNode r2 = fun(root.right);if(r1 != null && r2 != null){r1.right = root.right;root.right = root.left;root.left = null;return r2;}if(r1 == null && r2 != null){return r2;}if(r2 == null && r1 != null){root.right = root.left;root.left = null;return r1;}return root;}
}

第二种解法

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public void flatten(TreeNode root) {if(root == null){return;}TreeNode r1 = root.left;TreeNode r2 = root.right;flatten(root.left);flatten(root.right);root.left = null;root.right = r1;TreeNode p = root;while(p.right != null){p = p.right;}p.right = r2;}
}