赞
踩
个人博客主页:http://myblog.nxx.nx.cn
代码GitHub地址:https://github.com/nx-xn2002/Data_Structure.git
题目链接:
https://leetcode.cn/problems/balanced-binary-tree/
题目描述:
给定一个二叉树,判断它是否是 平衡二叉树
思路:
题目中平衡二叉树指左右子树最大深度差不超过 1,因此按之前的思路,求出树的最大深度和最小深度,最后判断差值绝对值是否小于等于 1 即可。
代码实现:
class Solution { public boolean isBalanced(TreeNode root) { if (root == null) { return true; } int min = getMinDepth(root); int max = getMaxDepth(root); return Math.abs(max - min) <= 1; } private static int getMinDepth(TreeNode root) { if (root == null) { return 0; } if (root.left == null && root.right == null) { return 1; } int res = Integer.MAX_VALUE; if (root.left != null) { res = Math.min(res, getMinDepth(root.left)); } if (root.right != null) { res = Math.min(res, getMinDepth(root.right)); } return res + 1; } private static int getMaxDepth(TreeNode root) { if (root == null) { return 0; } if (root.left == null && root.right == null) { return 1; } int res = Integer.MIN_VALUE; if (root.left != null) { res = Math.max(res, getMaxDepth(root.left)); } if (root.right != null) { res = Math.max(res, getMaxDepth(root.right)); } return res + 1; } }
题目链接:
https://leetcode.cn/problems/binary-tree-paths/
题目描述:
给你一个二叉树的根节点 root
,按 任意顺序 ,返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
思路:
本题直接使用回溯法就行了,使用一个 ArrayList
暂存路径,当递归变量到叶子结点时,将路径保存并返回,只需要注意每次递归后删除路径数组最后一个元素恢复原状态即可
代码实现:
class Solution { List<String> res = new ArrayList<>(); List<Integer> temp = new ArrayList<>(); public List<String> binaryTreePaths(TreeNode root) { if (root == null) { return res; } traversal(root); return res; } private void traversal(TreeNode root) { temp.add(root.val); if (root.left == null && root.right == null) { res.add(handel(temp)); } if (root.left != null) { traversal(root.left); temp.remove(temp.size() - 1); } if (root.right != null) { traversal(root.right); temp.remove(temp.size() - 1); } } private String handel(List<Integer> a) { StringBuilder str = new StringBuilder(); for (int i = 0; i < a.size() - 1; i++) { str.append(a.get(i)); str.append("->"); } str.append(a.get(a.size() - 1)); return str.toString(); } }
题目链接:
https://leetcode.cn/problems/sum-of-left-leaves/
题目描述:
给定二叉树的根节点 root
,返回所有左叶子之和。
思路:
本题也是简单题,通过递归返回所有左叶子节点的值即可,但需要注意,虽然是返回左节点的值,依然需要对右节点进行遍历,右节点有可能也存在左叶子节点。
代码实现:
class Solution { public int sumOfLeftLeaves(TreeNode root) { if (root == null) { return 0; } if (root.left == null && root.right == null) { return 0; } int leftValue = sumOfLeftLeaves(root.left); if (root.left != null && root.left.left == null && root.left.right == null) { leftValue = root.left.val; } int rightValue = sumOfLeftLeaves(root.right); return leftValue + rightValue; } }
题目链接:
https://leetcode.cn/problems/count-complete-tree-nodes/
题目描述:
给你一棵 完全二叉树 的根节点 root
,求出该树的节点个数。
完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h
层,则该层包含 1~ 2h
个节点。
思路:
本题直接使用层序遍历计算节点数量即可
代码实现:
class Solution { public int countNodes(TreeNode root) { int res = 0; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); queue.add(null); while (queue.peek() != null) { TreeNode temp = queue.poll(); while (temp != null) { res++; if (temp.left != null) { queue.add(temp.left); } if (temp.right != null) { queue.add(temp.right); } temp = queue.poll(); } queue.add(null); } return res; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。