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;}
}