二叉树LC总结（一）：https://developer.aliyun.com/article/1534446
7.二叉树的层序遍历：
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); List<List<Integer>> res = new ArrayList<>(); if (root != null) queue.add(root); while (!queue.isEmpty()) { List<Integer> tmp = new ArrayList<>(); for(int i = queue.size(); i > 0; i--) { TreeNode node = queue.poll(); tmp.add(node.val); if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } res.add(tmp); } return res; } } ———————————————— 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 原文链接：https://blog.csdn.net/m0_60469045/article/details/136693632
8.验证二叉搜索树：
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
输入：root = [2,1,3]
输出：true
class Solution { public boolean isValidBST(TreeNode root) { return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE); } public boolean isValidBST(TreeNode node, long lower, long upper) { if (node == null) { return true; } if (node.val <= lower || node.val >= upper) { return false; } return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper); } } ———————————————— 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 原文链接：https://blog.csdn.net/m0_60469045/article/details/136693632
9.二叉树展开为链表：
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用
TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
class Solution { public void flatten(TreeNode root) { if (root == null) { return; //Base case: 空树 } if (root.left == null) { flatten(root.right); //若左子树为空，直接flatten右子树即可 } else { //否则，先将左右子树分别flatten flatten(root.left); flatten(root.right); TreeNode oldRight = root.right; //用一个TreeNode变量保存faltten之后的右子树 TreeNode curr = root.left; //设置curr变量并循环，找到左子树的最右子节点 while (curr.right != null) { curr = curr.right; } curr.right = oldRight; //将与右子树挂载到左子树的最后 root.right = root.left; //将左子树挂载为原根节点的右子树 root.left = null; //根节点左子树设为空 } } } ———————————————— 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 原文链接：https://blog.csdn.net/m0_60469045/article/details/136693632
10.从前序与中序遍历序列构造二叉树：
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
class Solution { private Map<Integer, Integer> indexMap; public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) { if (preorder_left > preorder_right) { return null; } // 前序遍历中的第一个节点就是根节点 int preorder_root = preorder_left; // 在中序遍历中定位根节点 int inorder_root = indexMap.get(preorder[preorder_root]); // 先把根节点建立出来 TreeNode root = new TreeNode(preorder[preorder_root]); // 得到左子树中的节点数目 int size_left_subtree = inorder_root - inorder_left; // 递归地构造左子树，并连接到根节点 // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素 root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1); // 递归地构造右子树，并连接到根节点 // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素 root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right); return root; } public TreeNode buildTree(int[] preorder, int[] inorder) { int n = preorder.length; // 构造哈希映射，帮助我们快速定位根节点 indexMap = new HashMap<Integer, Integer>(); for (int i = 0; i < n; i++) { indexMap.put(inorder[i], i); } return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1); } } ———————————————— 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 原文链接：https://blog.csdn.net/m0_60469045/article/details/136693632
11.二叉搜索树中第K小的元素：
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
输入：root = [3,1,4,null,2], k = 1
输出：1
class Solution { public int kthSmallest(TreeNode root, int k) { Deque<TreeNode> stack = new ArrayDeque<TreeNode>(); while (root != null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); --k; if (k == 0) { break; } root = root.right; } return root.val; } } ———————————————— 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 原文链接：https://blog.csdn.net/m0_60469045/article/details/136693632
12.二叉树的右视图：
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
//dfs class Solution { private List<Integer> ans; public List<Integer> rightSideView(TreeNode root) { ans = new ArrayList<>(); dfs(root, 0); return ans; } private void dfs(TreeNode node, int depth) { if (node == null) return; if (ans.size() <= depth) ans.add(node.val); else ans.set(depth, node.val); dfs(node.left, depth + 1); dfs(node.right, depth + 1); } } //bfs class Solution { public List<Integer> rightSideView(TreeNode root) { List<Integer> ans = new ArrayList<>(); if (root == null) return ans; Queue<TreeNode> q = new LinkedList<>(); q.offer(root); int count; while (!q.isEmpty()) { count = q.size(); for (int i = 0; i < count; i++) { TreeNode node = q.poll(); if (node.left != null) q.offer(node.left); if (node.right != null) q.offer(node.right); if (i == count - 1) ans.add(node.val); } } return ans; } } ———————————————— 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 原文链接：https://blog.csdn.net/m0_60469045/article/details/136693632
