二叉树的递归遍历|前中后序遍历、最大深度、最大直径
2023-12-25 06:18:46
二叉树的递归遍历
前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
res.add(root.val);
if (root.left != null) {
res.addAll(preorderTraversal(root.left));
}
if (root.right != null) {
res.addAll(preorderTraversal(root.right));
}
return res;
}
中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
if (root.left != null) {
res.addAll(inorderTraversal(root.left));
}
res.add(root.val);
if (root.right != null) {
res.addAll(inorderTraversal(root.right));
}
return res;
}
后序遍历
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
if (root.left != null) {
res.addAll(postorderTraversal(root.left));
}
if (root.right != null) {
res.addAll(postorderTraversal(root.right));
}
res.add(root.val);
return res;
}
层序遍历
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return res;
}
helper(root, 0);
return res;
}
private void helper(TreeNode root, int level) {
if (level == res.size()) {
res.add(new ArrayList<>());
}
res.get(level).add(root.val);
if (root.left != null) {
helper(root.left, level+1);
}
if (root.right != null) {
helper(root.right, level+1);
}
}
最大深度
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
最大直径
int maxd = 0;
public int diameterOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}
depth(root);
return maxd;
}
private int depth(TreeNode root) {
if (root == null) {
return 0;
}
int left = depth(root.left);
int right = depth(root.right);
maxd = Math.max(left+right, maxd); //获得当前节点的直径为 左右子树深度和
return Math.max(left, right) + 1; //当前节点的深度为左右子树深度的最大值+1
}
文章来源:https://blog.csdn.net/weixin_43217281/article/details/135189896
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!