给定一个二叉树,检查它是否是镜像对称的。
image
上图为对称二叉树
image
上图的二叉树则不是镜像的
判断是否是镜像,需要去判断二叉树的里侧和外侧是否相同。
这就需要去判断根节点下左子树与右子树里侧和外侧是否相等。比较的方法是拿左子树的 “左-右-中” 节点和右子树的“右-左-中”为顺序的节点做比较。
这题用递归的方式解比较方便,递归的思路如下:
public boolean isSymmetric1(TreeNode root) {
return compare(root.left, root.right);
}
private boolean compare(TreeNode left, TreeNode right) {
if (left == null && right != null) {
return false;
}
if (left != null && right == null) {
return false;
}
if (left == null && right == null) {
return true;
}
if (left.val != right.val) {
return false;
}
// 比较外侧
boolean compareOutside = compare(left.left, right.right);
// 比较内侧
boolean compareInside = compare(left.right, right.left);
return compareOutside && compareInside;
}
时间复杂度:O(N),其中 N 是树的节点数。对每个节点访问一次。
空间复杂度:O(H),其中 H 是树的高度
二叉树的深度是指根节点到最远叶子节点的最长路径上的节点数。
我们可以通过递归的方式求解此题:
代码如下:
class solution {
public:
int getdepth(treenode node) {
if (node == null) return 0;
int leftdepth = getdepth(node.left); // 左
int rightdepth = getdepth(node.right); // 右
int depth = 1 + Math.max(leftdepth, rightdepth); // 中
return depth;
}
int maxdepth(treenode root) {
return getdepth(root);
}
};
时间复杂度:O(N),其中 N 是树的节点数。对每个节点访问一次。
空间复杂度:O(H),其中 H 是树的高度
同理,该方法适用于求 N 叉树的最大深度,代码如下:
// 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 int maxDepth(Node root) {
if (root == null) {
return 0;
} else if (root.children.isEmpty()) {
return 1;
} else {
List<Integer> heights = new LinkedList<>();
// 循环求出每个子树的高度
for (Node item : root.children) {
heights.add(maxDepth(item));
}
return Collections.max(heights) + 1;
}
}
}
时间复杂度:O(N),其中 N 是树的节点数。对每个节点访问一次。
空间复杂度:O(H),其中 H 是树的高度
说明:最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
这里有个误区需要解释一下,是从根节点到最近的叶子节点,如果根节点没有左子树或者右子树,很多人就觉得最小深度为 1,这是不对的。是从根节点到最近叶子节点的最短路径上的节点数量才是最小深度。
可以看出, 求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。
代码如下:
class Solution {
/**
* 递归法,相比求MaxDepth要复杂点
* 因为最小深度是从根节点到最近**叶子节点**的最短路径上的节点数量
*/
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
if (root.left == null) {
return rightDepth + 1;
}
if (root.right == null) {
return leftDepth + 1;
}
// 左右结点都不为null
return Math.min(leftDepth, rightDepth) + 1;
}
}
时间复杂度:O(N),其中 N 是树的节点数。对每个节点访问一次。
空间复杂度:O(H),其中 H 是树的高度。
给出一个完全二叉树,求出该树的节点个数。
此题可用求二叉树的最大深度的方式来求出,代码如下:
class solution {
public:
int getdepth(treenode node) {
if (node == null) return 0;
int leftdepth = getdepth(node.left); // 左
int rightdepth = getdepth(node.right); // 右
int depth = 1 + leftdepth, rightdepth; // 中
return depth;
}
int maxdepth(treenode root) {
return getdepth(root);
}
};
时间复杂度:O(n),n 为二叉树节点个数 空间复杂度:O(h),h 为 树的高度
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
既然是要求比较高度,则我们可以用到后序遍历的方式。
代码如下:
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;
}
// 左右子树高度差大于1,return -1表示已经不是平衡树了
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
return Math.max(leftHeight, rightHeight) + 1;
}
}
给定一个二叉树,返回所有从根节点到叶子节点的路径。
根据题意要从根节点到叶子节点的路径,所以需要前序遍历。
代码如下:
//解法一
class Solution {
/**
* 递归法
*/
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
if (root == null) {
return res;
}
List<Integer> paths = new ArrayList<>();
traversal(root, paths, res);
return res;
}
private void traversal(TreeNode root, List<Integer> paths, List<String> res) {
paths.add(root.val);
// 叶子结点
if (root.left == null && root.right == null) {
// 输出
StringBuilder sb = new 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);// 回溯
}
}
}
计算给定二叉树的所有左叶子之和。
首先要判断这棵二叉树有没有左叶子,就必须要通过节点的父节点来判断其左孩子是不是左叶子,判断代码如下:
if (root.left != null && root.left.left == null && root.left.right == null) { // 中
midValue = root.left.val;
}
用后序遍历找出所有的左叶子节点数值之和,递归方式如下:
代码如下:
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;
}
}
给定一个二叉树,在树的最后一行找到最左边的值。
本题比较容易下手的解题方式可以用层序遍历的方法,找到最后一行的最左边。
但是也可以用递归法来实现,首先可以明确深度最大的叶子节点一定是最后一行,那如何找最左边的呢?我们可以使用前序遍历,优先从左边开始搜索。
代码如下:
// 递归法
class Solution {
private int Deep = -1;
private int value = 0;
public int findBottomLeftValue(TreeNode root) {
value = root.val;
findLeftValue(root,0);
return value;
}
private void findLeftValue (TreeNode root,int deep) {
if (root == null) return;
if (root.left == null && root.right == null) {
if (deep > Deep) {
value = root.val;
Deep = deep;
}
}
if (root.left != null) findLeftValue(root.left,deep + 1);
if (root.right != null) findLeftValue(root.right,deep + 1);
}
}
给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
利用递归来解答此题:
代码如下:
class solution {
public boolean haspathsum(treenode root, int targetsum) {
if (root == null) {
return false;
}
targetsum -= root.val;
// 叶子结点
if (root.left == null && root.right == null) {
return targetsum == 0;
}
if (root.left != null) {
boolean left = haspathsum(root.left, targetsum);
if (left) {// 已经找到
return true;
}
}
if (root.right != null) {
boolean right = haspathsum(root.right, targetsum);
if (right) {// 已经找到
return true;
}
}
return false;
}
}
// 精简后的代码
class solution {
public boolean haspathsum(treenode root, int targetsum) {
if (root == null) return false; // 为空退出
// 叶子节点判断是否符合
if (root.left == null && root.right == null) return root.val == targetsum;
// 求两侧分支的路径和
return haspathsum(root.left, targetsum - root.val) || haspathsum(root.right, targetsum - root.val);
}
}
给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
解题思路与上一题相似,只是需要记录路径。
代码如下:
class solution {
public list<list<integer>> pathsum(treenode root, int targetsum) {
list<list<integer>> res = new arraylist<>();
if (root == null) return res; // 非空判断
list<integer> path = new linkedlist<>();
preorderdfs(root, targetsum, res, path);
return res;
}
public void preorderdfs(treenode root, int targetsum, list<list<integer>> res, list<integer> path) {
path.add(root.val);
// 遇到了叶子节点
if (root.left == null && root.right == null) {
// 找到了和为 targetsum 的路径
if (targetsum - root.val == 0) {
res.add(new arraylist<>(path));
}
return; // 如果和不为 targetsum,返回
}
if (root.left != null) {
preorderdfs(root.left, targetsum - root.val, res, path);
path.remove(path.size() - 1); // 回溯
}
if (root.right != null) {
preorderdfs(root.right, targetsum - root.val, res, path);
path.remove(path.size() - 1); // 回溯
}
}
}
好了,关于二叉树属性的总结到这里就结束了。相信看完这篇文章,你会对二叉树属性有一定的了解,感谢你的阅读。
本文分享自 HelloWorld杰少 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!