101.对称二叉树

linwt · linwt · commit 2bd0aeb9ed17 · 2021-11-13T23:02:02.000+08:00
104.二叉树最大深度
226.翻转二叉树
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -1,5 +1,8 @@
 94. 二叉树的中序遍历
+101. 对称二叉树
 102. 二叉树的层序遍历
+104. 二叉树的最大深度
 144. 二叉树的前序遍历
 145. 二叉树的后序遍历
+226. 翻转二叉树
 589. N叉树的前序遍历
diff --git a/leetcode_Java/Solution0101.java b/leetcode_Java/Solution0101.java
@@ -0,0 +1,91 @@
+// 对称二叉树
+
+
+/**
+ * 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;
+ *     }
+ * }
+ */
+
+
+/*
+* 递归思路：
+* 1、方法定义：
+*    1）由于要判断两个节点对应的左右子节点值是否相同，原方法入参只有一个节点不够用，需要再定义一个有两个节点作为入参的方法
+*    2）不管是原方法还是新方法，其返回类型和返回结果都跟题目要求的返回类型和返回结果一致
+* 2、方法功能：
+*    1）入参是两个节点，判断两个节点是否相同
+*    2）节点都为空、节点都不为空且值相等则返回true；节点只有一个不为空、节点都不为空但值不相等则返回false
+* 3、递归逻辑：
+*    1）两个节点的左右子节点同样可以调用这个方法，判断节点是否相同，得到true或false的结果
+*    2）当前层节点对称，才会继续递归下一层
+*    3）每一层，每两个节点作为入参，调用方法，都得到了true或false的结果
+*    4）上一层使用下一层的结果，将下一层多个结果进行与运算，得到下一层的节点是否对称
+* */
+class Solution {
+    public boolean isSymmetric(TreeNode root) {
+        if (root == null) {
+            return true;
+        }
+        return isSameTree(root.left, root.right);
+    }
+
+    public boolean isSameTree(TreeNode p, TreeNode q) {
+        if (p == null && q == null) {
+            return true;
+        }
+        if (p != null && q != null && p.val == q.val) {
+            boolean l = isSameTree(p.left, q.right);
+            boolean r = isSameTree(p.right, q.left);
+            return l && r;
+        }
+        return false;
+    }
+}
+
+
+/*
+* 迭代思路：
+* 1、定义数据结构：队列按序存放节点
+* 2、队列初始化：将根节点的左右节点存入队列
+* 3、迭代逻辑：
+*    1）遍历队列，弹出两个节点，比较是否相同
+*    2）不相同则返回false。都为空、都不为空且值相等，则存入两个节点对应的下一层的四个左右子节点节点
+*    3）最终节点都存入了队列，且弹出判断都两两相同，则返回true
+* */
+class Solution {
+    public boolean isSymmetric(TreeNode root) {
+        if (root == null) {
+            return true;
+        }
+        Queue<TreeNode> queue = new LinkedList<>();
+        queue.offer(root.left);
+        queue.offer(root.right);
+        while (!queue.isEmpty()) {
+            TreeNode p = queue.poll();
+            TreeNode q = queue.poll();
+            if (p == null && q == null) {
+                continue;
+            }
+            if (p != null && q != null && p.val == q.val) {
+                queue.offer(p.left);
+                queue.offer(q.right);
+                queue.offer(p.right);
+                queue.offer(q.left);
+                continue;
+            }
+            return false;
+        }
+        return true;
+    }
+}
diff --git a/leetcode_Java/Solution0104.java b/leetcode_Java/Solution0104.java
@@ -0,0 +1,72 @@
+// 二叉树的最大深度
+
+
+/**
+ * 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;
+ *     }
+ * }
+ */
+
+
+/*
+* 递归思路：
+* 1、方法功能：入参是一个节点，节点为空返回0，节点不为空返回1
+* 2、递归逻辑：
+*    1）左右节点同样可以调用这个方法，得到0或1的结果
+*    2）每一层，每个节点，调用方法，都得到了0或1的结果
+*    3）上一层使用下一层的结果，取下一层左右节点结果的最大值，累加到当前层，从而得到二叉树的最大深度
+* */
+class Solution {
+    public int maxDepth(TreeNode root) {
+        if (root == null) {
+            return 0;
+        }
+        int l = maxDepth(root.left);
+        int r = maxDepth(root.right);
+        return 1 + Math.max(l, r);
+    }
+}
+
+
+/*
+* 迭代思路：
+* 1、定义数据结构：队列存放每一层的节点
+* 2、定义局部变量：deep记录深度；count记录每层节点个数，以便标记队列节点每层结束位置
+* 2、实现逻辑：层序遍历，遍历当前层节点时，把下一层节点存入队列，每一层遍历结束后，深度加1，最终得到最大深度
+* */
+class Solution {
+    public int maxDepth(TreeNode root) {
+        if (root == null) {
+            return 0;
+        }
+        int deep = 0;
+        int count;
+        Queue<TreeNode> queue = new LinkedList<>();
+        queue.offer(root);
+        while (!queue.isEmpty()) {
+            count = queue.size();
+            while (count > 0) {
+                root = queue.poll();
+                if (root.left != null) {
+                    queue.offer(root.left);
+                }
+                if (root.right != null) {
+                    queue.offer(root.right);
+                }
+                count--;
+            }
+            deep++;
+        }
+        return deep;
+    }
+}
diff --git a/leetcode_Java/Solution0226.java b/leetcode_Java/Solution0226.java
@@ -0,0 +1,81 @@
+// 翻转二叉树
+
+
+/**
+ * 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;
+ *     }
+ * }
+ */
+
+
+/*
+* 递归思路：
+* 1、方法功能：节点为空时返回空，节点不为空时把节点的左右子节点交换一下
+* 2、递归逻辑：
+*    1）每一层，每个节点，都需要将其左右子节点交换，就需要调用同个方法
+*    2）方法功能是交换节点，不需要接收下一层的返回值给上一层使用
+*    3）所有节点都交换完成后，返回根节点
+* */
+class Solution {
+    public TreeNode invertTree(TreeNode root) {
+        if (root == null) {
+            return null;
+        }
+        TreeNode tempNode = root.left;
+        root.left = root.right;
+        root.right = tempNode;
+        invertTree(root.left);
+        invertTree(root.right);
+        return root;
+    }
+}
+
+
+/*
+* 迭代思路：
+* 1、定义数据结构：栈存放要交换其左右子节点的节点
+* 2、保留根节点指针：根节点指针赋值给新节点指针，使用新节点指针遍历节点，最终需要返回根节点指针
+*   （实例对象存储在堆内存中，对象变量存储在栈中，对象变量就是一个引用，也表示指针，对象变量的赋值就是指针指向的改变）
+* 3、栈初始化：将新节点存入栈
+* 4、迭代逻辑：
+*    1）弹出节点，判断节点的左右子节点是否都为空，为空则跳过
+*    2）左右子节点不都为空，则进行节点交换
+*    3）然后将不为空的节点存入栈中
+*    4）遍历了所有节点且交换了其左右子节点，则翻转二叉树完成，返回根节点
+* */
+class Solution {
+    public TreeNode invertTree(TreeNode root) {
+        if (root == null) {
+            return null;
+        }
+        Stack<TreeNode> stack = new Stack<>();
+        TreeNode curNode = root;
+        stack.push(curNode);
+        while (!stack.isEmpty()) {
+            curNode = stack.pop();
+            if (curNode.left == null && curNode.right == null) {
+                continue;
+            }
+            TreeNode tempNode = curNode.left;
+            curNode.left = curNode.right;
+            curNode.right = tempNode;
+            if (curNode.left != null) {
+                stack.push(curNode.left);
+            }
+            if (curNode.right != null) {
+                stack.push(curNode.right);
+            }
+        }
+        return root;
+    }
+}
