简洁手机导航网站模板下载安装,佛山顺德网站设计公司,网站群建设方案.doc,外贸网络推广信提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣226. 翻转二叉树二、力扣116. 填充每个节点的下一个右侧节点指针三、力扣114. 二叉树展开为链表 二叉树解题的思维模式分两类#xff1a; 1、是否可以… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、力扣226. 翻转二叉树二、力扣116. 填充每个节点的下一个右侧节点指针三、力扣114. 二叉树展开为链表 二叉树解题的思维模式分两类 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;}
}
