新乐市建设银行网站,广州财税公司排行榜,手机网站整站源码,沈阳男科正规医院目录 110. 平衡二叉树题目描述参考代码 257. 二叉树的所有路径题目描述参考代码 404.左叶子之和题目描述参考代码 110. 平衡二叉树
题目描述
给定一个二叉树#xff0c;判断它是否是高度平衡的二叉树。
本题中#xff0c;一棵高度平衡二叉树定义为#xff1a; 一个二叉树… 目录 110. 平衡二叉树题目描述参考代码 257. 二叉树的所有路径题目描述参考代码 404.左叶子之和题目描述参考代码 110. 平衡二叉树
题目描述
给定一个二叉树判断它是否是高度平衡的二叉树。
本题中一棵高度平衡二叉树定义为 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 示例 1 输入root [3,9,20,null,null,15,7]
输出true示例 2 输入root [1,2,2,3,3,null,null,4,4]
输出false示例 3
输入root []
输出true提示
树中的节点数在范围 [0, 5000] 内-104 Node.val 104
参考代码
class Solution {/*** 递归法*/public boolean isBalanced(TreeNode root) {return getHeight(root) ! -1;}private int getHeight(TreeNode root) {if (root null) {return 0;}int leftHeight getHeight(root.left);if (leftHeight -1) {return -1;}int rightHeight getHeight(root.right);if (rightHeight -1) {return -1;}// 左右子树高度差大于1return -1表示已经不是平衡树了if (Math.abs(leftHeight - rightHeight) 1) {return -1;}return Math.max(leftHeight, rightHeight) 1;}
}class Solution {/*** 迭代法效率较低计算高度时会重复遍历* 时间复杂度O(n^2)*/public boolean isBalanced(TreeNode root) {if (root null) {return true;}StackTreeNode stack new Stack();TreeNode pre null;while (root! null || !stack.isEmpty()) {while (root ! null) {stack.push(root);root root.left;}TreeNode inNode stack.peek();// 右结点为null或已经遍历过if (inNode.right null || inNode.right pre) {// 比较左右子树的高度差输出if (Math.abs(getHeight(inNode.left) - getHeight(inNode.right)) 1) {return false;}stack.pop();pre inNode;root null;// 当前结点下没有要遍历的结点了} else {root inNode.right;// 右结点还没遍历遍历右结点}}return true;}/*** 层序遍历求结点的高度*/public int getHeight(TreeNode root) {if (root null) {return 0;}DequeTreeNode deque new LinkedList();deque.offer(root);int depth 0;while (!deque.isEmpty()) {int size deque.size();depth;for (int i 0; i size; i) {TreeNode poll deque.poll();if (poll.left ! null) {deque.offer(poll.left);}if (poll.right ! null) {deque.offer(poll.right);}}}return depth;}
}class Solution {/*** 优化迭代法针对暴力迭代法的getHeight方法做优化利用TreeNode.val来保存当前结点的高度这样就不会有重复遍历* 获取高度算法时间复杂度可以降到O(1)总的时间复杂度降为O(n)。* 时间复杂度O(n)*/public boolean isBalanced(TreeNode root) {if (root null) {return true;}StackTreeNode stack new Stack();TreeNode pre null;while (root ! null || !stack.isEmpty()) {while (root ! null) {stack.push(root);root root.left;}TreeNode inNode stack.peek();// 右结点为null或已经遍历过if (inNode.right null || inNode.right pre) {// 输出if (Math.abs(getHeight(inNode.left) - getHeight(inNode.right)) 1) {return false;}stack.pop();pre inNode;root null;// 当前结点下没有要遍历的结点了} else {root inNode.right;// 右结点还没遍历遍历右结点}}return true;}/*** 求结点的高度*/public int getHeight(TreeNode root) {if (root null) {return 0;}int leftHeight root.left ! null ? root.left.val : 0;int rightHeight root.right ! null ? root.right.val : 0;int height Math.max(leftHeight, rightHeight) 1;root.val height;// 用TreeNode.val来保存当前结点的高度return height;}
}257. 二叉树的所有路径
题目描述
给你一个二叉树的根节点 root 按 任意顺序 返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1 输入root [1,2,3,null,5]
输出[1-2-5,1-3]示例 2
输入root [1]
输出[1]提示
树中节点的数目在范围 [1, 100] 内-100 Node.val 100
参考代码
//解法一//方式一
class Solution {/*** 递归法*/public ListString binaryTreePaths(TreeNode root) {ListString res new ArrayList();// 存最终的结果if (root null) {return res;}ListInteger paths new ArrayList();// 作为结果中的路径traversal(root, paths, res);return res;}private void traversal(TreeNode root, ListInteger paths, ListString res) {paths.add(root.val);// 前序遍历中// 遇到叶子结点if (root.left null root.right null) {// 输出StringBuilder sb new StringBuilder();// StringBuilder用来拼接字符串速度更快for (int i 0; i paths.size() - 1; i) {sb.append(paths.get(i)).append(-);}sb.append(paths.get(paths.size() - 1));// 记录最后一个节点res.add(sb.toString());// 收集一个路径return;}// 递归和回溯是同时进行所以要放在同一个花括号里if (root.left ! null) { // 左traversal(root.left, paths, res);paths.remove(paths.size() - 1);// 回溯}if (root.right ! null) { // 右traversal(root.right, paths, res);paths.remove(paths.size() - 1);// 回溯}}
}//方式二
class Solution {ListString result new ArrayList();public ListString binaryTreePaths(TreeNode root) {deal(root, );return result;}public void deal(TreeNode node, String s) {if (node null)return;if (node.left null node.right null) {result.add(new StringBuilder(s).append(node.val).toString());return;}String tmp new StringBuilder(s).append(node.val).append(-).toString();deal(node.left, tmp);deal(node.right, tmp);}
}404.左叶子之和
题目描述
给定二叉树的根节点 root 返回所有左叶子之和。
示例 1 输入: root [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中有两个左叶子分别是 9 和 15所以返回 24示例 2:
输入: root [1]
输出: 0提示:
节点数在 [1, 1000] 范围内-1000 Node.val 1000
参考代码
class Solution {public int sumOfLeftLeaves(TreeNode root) {if (root null) return 0;int leftValue sumOfLeftLeaves(root.left); // 左int rightValue sumOfLeftLeaves(root.right); // 右int midValue 0;if (root.left ! null root.left.left null root.left.right null) { midValue root.left.val;}int sum midValue leftValue rightValue; // 中return sum;}
}
