Java算法练习4

- 1.1 [145. 二叉树的后序遍历](https://leetcode.cn/problems/binary-tree-postorder-traversal/)
- 1.2 [173. 二叉搜索树迭代器](https://leetcode.cn/problems/binary-search-tree-iterator/)
- 1.3 [98. 验证二叉搜索树](https://leetcode.cn/problems/validate-binary-search-tree/)
- 1.4 [102. 二叉树的层序遍历](https://leetcode.cn/problems/binary-tree-level-order-traversal/)
- 1.5 [429. N 叉树的层序遍历](https://leetcode.cn/problems/n-ary-tree-level-order-traversal/)
- 1.6 [513. 找树左下角的值](https://leetcode.cn/problems/find-bottom-left-tree-value/)
- 1.7 [404. 左叶子之和](https://leetcode.cn/problems/sum-of-left-leaves/)

1.1 145. 二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]

/*** 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 List<Integer> postorderTraversal(TreeNode root) {List list = new ArrayList<Integer>();lrp(root,list);return list;}public void lrp(TreeNode root,List<Integer> list){if(root == null) return;lrp(root.left,list);lrp(root.right,list);list.add(root.val);}
}

1.2 173. 二叉搜索树迭代器

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：

BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
int next()将指针向右移动，然后返回指针处的数字。

注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。

你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

示例：
输入
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // 返回 3
bSTIterator.next();    // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 20
bSTIterator.hasNext(); // 返回 False

/*** 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 BSTIterator {private int index;private List<Integer> list;public BSTIterator(TreeNode root) {list = new ArrayList<Integer>();index = 0;lpr(root,list);}public int next() {return list.get(index++);}public boolean hasNext() {return index<list.size();}public void lpr(TreeNode root,List<Integer> list){if(root == null) return;lpr(root.left,list);list.add(root.val);lpr(root.right,list);}
}/*** Your BSTIterator object will be instantiated and called as such:* BSTIterator obj = new BSTIterator(root);* int param_1 = obj.next();* boolean param_2 = obj.hasNext();*/

1.3 98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：
输入：root = [2,1,3]
输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 

/*** 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 {private List<Integer> list;public boolean isValidBST(TreeNode root) {list = new ArrayList<Integer>();lpr(root,list);for (int i = 1; i < list.size(); i++) {if(list.get(i) <= list.get(i-1)) return false;}return true;}public void lpr(TreeNode root,List<Integer> list){if(root == null) return;lpr(root.left,list);list.add(root.val);lpr(root.right,list);}}

1.4 102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：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 List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> list = new ArrayList<>();Queue<TreeNode> q = new LinkedList<>();q.offer(root);while(q.isEmpty() == false){ //判断队列是否为空，为空则证明遍历结束int size = q.size();List<Integer> level = new LinkedList();for(int i = 0;i < size; i++){TreeNode cur = q.poll(); //将节点出队列if(cur == null) continue; level.add(cur.val); q.offer(cur.left); //将左子节点放入队列q.offer(cur.right); //将右子节点放入队列}if(level.isEmpty() == false){ list.add(level);}}return list;}
}

1.5 429. N 叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};
*/class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> list = new ArrayList();Queue<Node> q = new LinkedList();q.offer(root);while(!q.isEmpty()){int size = q.size();List<Integer> level = new ArrayList();for(int i = 0;i < size; i++){Node cur = q.poll();if(cur == null) continue;level.add(cur.val);List<Node> l = cur.children; for(Node child : l){q.offer(child);}}if(!level.isEmpty()) list.add(level);}return list;}
}

1.6 513. 找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:
输入: root = [2,1,3]
输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

/*** 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 int findBottomLeftValue(TreeNode root) {int ret = 0;Queue<TreeNode> q = new LinkedList();q.offer(root);while(!q.isEmpty()){// int size = q.size();// for(int i = 0;i <size;i++){TreeNode cur = q.poll();if(cur == null) continue;q.offer(cur.right);q.offer(cur.left);ret = cur.val;// }}return ret;}
}

1.7 404. 左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。

示例 1：
输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
示例 2:
输入: root = [1]
输出: 0

/*** 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 {int sum = 0;public int sumOfLeftLeaves(TreeNode root) {if(root == null) return 0;if(root.left != null && root.left.left == null && root.left.right == null) sum += root.left.val;sumOfLeftLeaves(root.left);sumOfLeftLeaves(root.right);return sum;}
}