二叉树补充

linwt · linwt · commit 8065c2e9166d · 2022-05-05T07:50:29.000+08:00
diff --git a/leetcode_Java/DoneType.txt b/leetcode_Java/DoneType.txt
@@ -14,32 +14,32 @@
 
 
 一、树
-94. 二叉树的中序遍历
-96. 不同的二叉搜索树
-98. 验证二叉搜索树
-101. 对称二叉树
-102. 二叉树的层序遍历
-103. 二叉树的锯齿形层序遍历
-104. 二叉树的最大深度
-105. 从前序与中序遍历序列构造二叉树
-110. 平衡二叉树
-112. 路径总和
-113. 路径总和 II
-114. 二叉树展开为链表
-124. 二叉树中的最大路径和
-129. 求根节点到叶节点数字之和
-144. 二叉树的前序遍历
-145. 二叉树的后序遍历
-199. 二叉树的右视图
-226. 翻转二叉树
-236. 二叉树的最近公共祖先
-297. 二叉树的序列化与反序列化
-437. 路径总和 III
-538. 把二叉搜索树转换为累加树
-543. 二叉树的直径
-589. N叉树的前序遍历
-617. 合并二叉树
-662. 二叉树最大宽度
+94. 二叉树的中序遍历（递归，迭代，栈，列表，哈希表，莫里斯遍历）
+96. 不同的二叉搜索树（递归，动态规划）
+98. 验证二叉搜索树（递归，迭代）
+101. 对称二叉树（递归，迭代）
+102. 二叉树的层序遍历（递归，迭代）
+103. 二叉树的锯齿形层序遍历（递归，迭代）
+104. 二叉树的最大深度（递归，迭代）
+105. 从前序与中序遍历序列构造二叉树（递归，迭代）
+110. 平衡二叉树（递归）
+112. 路径总和（递归，迭代）
+113. 路径总和 II（递归，回溯，迭代）
+114. 二叉树展开为链表（迭代）
+124. 二叉树中的最大路径和（递归）
+129. 求根节点到叶节点数字之和（递归，迭代）
+144. 二叉树的前序遍历（递归，迭代）
+145. 二叉树的后序遍历（递归，迭代）
+199. 二叉树的右视图（迭代）
+226. 翻转二叉树（递归，迭代）
+236. 二叉树的最近公共祖先（递归）
+297. 二叉树的序列化与反序列化（递归，迭代）
+437. 路径总和 III（递归）
+538. 把二叉搜索树转换为累加树（递归）
+543. 二叉树的直径（递归）
+589. N叉树的前序遍历（递归，迭代）
+617. 合并二叉树（递归，迭代）
+662. 二叉树最大宽度（递归，迭代）
 
 
 二、回溯
diff --git a/leetcode_Java/Solution0094.java b/leetcode_Java/Solution0094.java
@@ -161,6 +161,23 @@ public List<Integer> inorderTraversal(TreeNode root) {
 *      插入左节点是替代了根节点的位置，根节点和其他结点右移一位
 *   5）最大索引的节点判断完左右节点后，移除索引列表的最大索引
 *   6）最终节点列表按序排序，遍历结点列表，将节点值存入结果列表
+*
+*       1
+*      / \
+*     2   3
+*        / \
+*       4   5
+*  节点列表：1
+*  索引列表：0
+* ====================
+*  节点列表：2 1 3
+*  索引列表：0 2
+* ====================
+*  节点列表：2 1 4 3 5
+*  索引列表：2 5
+* ====================
+*  节点列表：2 1 4 3 5
+*  索引列表：
 * */
 public class Solution0094 {
     public List<Integer> inorderTraversal(TreeNode root) {
diff --git a/leetcode_Java/Solution0098.java b/leetcode_Java/Solution0098.java
@@ -111,4 +111,30 @@ public List<Integer> inorderTraversal(TreeNode root) {
         inorderTraversal(root.right);
         return list;
     }
+}
+
+
+/*
+迭代：“94. 二叉树的中序遍历”，中序遍历过程更新保存前一节点值，当前节点值小于等于前一节点值，则无效，否则有效
+ */
+class Solution {
+    public boolean isValidBST(TreeNode root) {
+        long pre = Long.MIN_VALUE;
+        Deque<TreeNode> stack = new ArrayDeque<>();
+        TreeNode cur = root;
+        while (cur != null || !stack.isEmpty()) {
+            if (cur != null) {
+                stack.push(cur);
+                cur = cur.left;
+            } else {
+                cur = stack.pop();
+                if (cur.val <= pre) {
+                    return false;
+                }
+                pre = cur.val;
+                cur = cur.right;
+            }
+        }
+        return true;
+    }
 }
diff --git a/leetcode_Java/Solution0102.java b/leetcode_Java/Solution0102.java
@@ -113,7 +113,7 @@ public List<List<Integer>> levelOrder(TreeNode root) {
 3、一个节点处理过程和返回结果：当该层的子列表未创建时，则创建子列表加入全局列表中。将节点值加入该层的子列表中
 4、递归调用：左右节点同样需要加入对应层的子列表中，因此调用同样的方法处理
 5、递归顺序：前序遍历，要求层序遍历，所以要先处理根节点，再处理左右节点
-6、使用递归调用结果和返回结果：不用接收返回结构，将节点值加入子列表即可
+6、使用递归调用结果和返回结果：不用接收返回结果，将节点值加入子列表即可
 * */
 class Solution {
     List<List<Integer>> list = new ArrayList<>();
diff --git a/leetcode_Java/Solution0103.java b/leetcode_Java/Solution0103.java
@@ -19,7 +19,36 @@
 
 
 /*
-102.二叉树的层序遍历，加上是否反转标记，奇数层不变，偶数层反转子数组
+“102.二叉树的层序遍历”，奇数层正序插入节点值，偶数层逆序插入节点值
+ */
+class Solution {
+    List<List<Integer>> list = new ArrayList<>();
+
+    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
+        dfs(root, 1);
+        return list;
+    }
+
+    public void dfs(TreeNode root, int layer) {
+        if (root == null) {
+            return;
+        }
+        if (list.size() < layer) {
+            list.add(new ArrayList<>());
+        }
+        if (layer % 2 == 1) {
+            list.get(layer - 1).add(root.val);
+        } else {
+            list.get(layer - 1).add(0, root.val);
+        }
+        dfs(root.left, layer + 1);
+        dfs(root.right, layer + 1);
+    }
+}
+
+
+/*
+“102.二叉树的层序遍历”，加上是否反转标记，奇数层不变，偶数层反转子数组
  */
 class Solution {
     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
diff --git a/leetcode_Java/Solution0104.java b/leetcode_Java/Solution0104.java
@@ -58,11 +58,10 @@ public int maxDepth(TreeNode root) {
             return 0;
         }
         int deep = 0;
-        int count;
         Queue<TreeNode> queue = new LinkedList<>();
         queue.offer(root);
         while (!queue.isEmpty()) {
-            count = queue.size();
+            int count = queue.size();
             while (count > 0) {
                 root = queue.poll();
                 if (root.left != null) {
diff --git a/leetcode_Java/Solution0105.java b/leetcode_Java/Solution0105.java
@@ -90,4 +90,53 @@ public TreeNode buildTreeHelper(int[] preorder, int pStart, int pEnd, int[] inor
         root.right = buildTreeHelper(preorder, pStart + leftNum + 1, pEnd, inorder, iRootIndex + 1, iEnd);
         return root;
     }
+}
+
+
+/*
+迭代：
+1、用一个栈和一个指针辅助进行二叉树的构造。初始时栈中存放了根节点（前序遍历的第一个节点），指针指向中序遍历的第一个节点
+2、依次枚举前序遍历中除了第一个节点以外的每个节点
+  1）如果 index 恰好指向栈顶节点，那么不断地弹出栈顶节点并向右移动 index，并将当前节点作为最后一个弹出的节点的右儿子
+  2）如果 index 和栈顶节点不同，将当前节点作为栈顶节点的左儿子
+  3）无论是哪一种情况，最后都将当前的节点入栈
+
+preorder = [3, 9, 8, 5, 4, 10, 20, 15, 7]
+inorder = [4, 5, 8, 10, 9, 3, 15, 20, 7]
+        3
+       / \
+      9  20
+     /  /  \
+    8  15   7
+   / \
+  5  10
+ /
+4
+ */
+class Solution {
+    public TreeNode buildTree(int[] preorder, int[] inorder) {
+        if (preorder == null || preorder.length == 0) {
+            return null;
+        }
+        TreeNode root = new TreeNode(preorder[0]);
+        Deque<TreeNode> stack = new ArrayDeque<>();
+        stack.push(root);
+        int inorderIndex = 0;
+        for (int i = 1; i < preorder.length; i++) {
+            int preorderVal = preorder[i];
+            TreeNode node = stack.peek();
+            if (node.val != inorder[inorderIndex]) {
+                node.left = new TreeNode(preorderVal);
+                stack.push(node.left);
+            } else {
+                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
+                    node = stack.pop();
+                    inorderIndex++;
+                }
+                node.right = new TreeNode(preorderVal);
+                stack.push(node.right);
+            }
+        }
+        return root;
+    }
 }
diff --git a/leetcode_Java/Solution0110.java b/leetcode_Java/Solution0110.java
@@ -20,7 +20,7 @@
 
 /*
 剑指offer 39.平衡二叉树
-1、本题需要两个递归方法，一个是递归计算每个节点的深度，一个是递归判断每个节点是否平衡
+1、本题需要两个递归方法，一个是递归计算每个节点的深度，一个是递归判断每个节点是否平衡。自顶向下
 2、递归计算节点深度
   1）方法功能：入参是一个节点，返回该节点的深度
   2）终止条件：节点为空时返回0
@@ -50,7 +50,7 @@ private int treeDepth(TreeNode root) {
 
 
 /*
-递归 + 记忆存储：
+递归 + 记忆存储：自顶向下
 1、计算深度递归函数
   1）方法功能：入参是一个节点，返回节点的深度
   2）终止条件：节点为空时返回0
@@ -94,8 +94,8 @@ private int treeDepth(TreeNode root) {
 
 
 /*
-递归 + 平衡标志：
-计算节点深度递归函数
+递归 + 平衡标志：自底向上
+计算节点深度递归函数：计算深度的同时，利用深度判断是否平衡
 1、方法功能：入参是一个节点，返回节点的深度
 2、终止条件：节点为空时返回0
 3、一个节点处理过程和返回结果：节点不为空时返回1
