【算法系列之二叉树I】leetcode226.翻转二叉树

news/2024/7/5 2:38:38

非递归实现前序遍历

力扣题目链接

解决思路

  1. 前序遍历，中左右。
  2. 先放右节点，后放左节点。

Java实现

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        //中左右
        Stack<TreeNode> stack = new Stack<>();
       
        List<Integer> res = new ArrayList<>();
        if(root==null){
            return res;
        }
         stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
            res.add(node.val);
        }
        return res;
    }
}

非递归实现中序遍历

力扣题目链接

解决思路

  1. 左中右
  2. 使用指针记录当前遍历的节点，挨个将左节点放入栈中。
  3. 不断从栈中弹出节点，栈里面的元素是左中。将右节点压入栈中。

Java实现

class Solution_LC94 {
    public List<Integer> inorderTraversal(TreeNode root) {
        //左中右
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {

                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                res.add(cur.val);
                cur = cur.right;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        //[1,null,2,3]
        List<Integer> res = new Solution_LC94().inorderTraversal(new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null)));
        System.out.println(res);
    }
}

非递归实现后续遍历

力扣题目链接

解决思路

  1. 先序遍历是中左右，后续遍历是左右中

Java实现

class Solution_LC145 {

    public List<Integer> postorderTraversal(TreeNode root) {
        //后序遍历  左右中     反过来   中右左
        Stack<TreeNode> stack = new Stack<>();

        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
            res.add(node.val);
        }
        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args) {
        List<Integer> res = new Solution_LC145().postorderTraversal(new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null)));
        System.out.println(res);
    }

}

226.翻转二叉树

力扣题目链接

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

解决思路

  1. 可以使用前序遍历，不能使用中序遍历
  2. 先换左节点，再换右节点，最后左右节点。

Java实现

class Solution_LC226 {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        invertTree(root.left);
        invertTree(root.right);
        swap(root);
        return root;
    }

    private void swap(TreeNode root) {
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}

101. 对称二叉树

力扣题目链接

给你一个二叉树的根节点 root ， 检查它是否轴对称。

输入：root = [1,2,2,3,4,4,3]
输出：true

解决思路

  1. 左右节点比较。左节点为空，右节点不为空，直接返回false。
  2. 比较的左孩子的左节点和右孩子的右节点。

Java实现

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        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;
        }
        return compare(left.left, right.right) && compare(left.right, right.left);
    }

    public static void main(String[] args) {
        boolean res = new Solution().isSymmetric(new TreeNode(1, new TreeNode(2, new TreeNode(3), new TreeNode(4)), new TreeNode(2, new TreeNode(4), new TreeNode(3))));
        System.out.println(res);
    }
}

104.二叉树的最大深度

力扣题目链接

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 `[3,9,20,null,null,15,7]`，
返回它的最大深度 3 。

解决思路

  1. 终止条件，如果root为空，高度为0
  2. 递推逻辑，比较左右节点的高度，较大值+1。

Java实现

递归实现

class Solution_LC104 {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

层序遍历

class Solution_LC101_II {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            depth++;
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return depth;
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1, new TreeNode(2, new TreeNode(4), null), new TreeNode(3, null, new TreeNode(5)));
//        [1,2,3,4,null,null,5]
        int res = new Solution_LC101_II().maxDepth(treeNode);
        System.out.println(res);
    }
}

559.n叉树的最大深度

力扣题目链接

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

输入：root = [1,null,3,2,4,null,5,6]
输出：3

解决思路

  1. 思路同上。

Java实现

递归实现

class Solution_LC559 {
    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }
        int depth = 0;
        for (int i = 0; i < root.children.size(); i++) {
            depth = Math.max(depth, maxDepth(root.children.get(i)));
        }
        return depth + 1;
    }
}

111.二叉树的最小深度

力扣题目链接

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明：**叶子节点是指没有子节点的节点。

解决思路

  1. 最近叶子节点。
  2. 如果左节点为空，获取右子树+1；如果右节点为空，获取左子树的高度+1。空节点不在计算范围内。

Java实现

class Solution_LC111 {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null) {
            return minDepth(root.right) + 1;
        }
        if (root.right == null) {
            return minDepth(root.left) + 1;
        }
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}

222.完全二叉树的节点个数

力扣题目链接

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

输入：root = [1,2,3,4,5,6]
输出：6

解决思路

  1. 递归实现

Java实现

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int count = 1;
        if (root.left != null) {
            count += countNodes(root.left);
        }
        if (root.right != null) {
            count += countNodes(root.right);
        }
        return count;
    }
}

110.平衡二叉树

力扣题目链接

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

输入：root = [3,9,20,null,null,15,7]
输出：true

解决思路

  1. 获取当前节点的左子树的高度
  2. 判断左右高度是否小于等于1，且左子树是否平衡，右子树是否平衡。

Java实现

class Solution_LC110 {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return Math.abs(getDepth(root.left) - getDepth(root.right)) <= 1 && isBalanced(root.right) && isBalanced(root.left);
    }

    private Integer getDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getDepth(root.left), getDepth(root.right)) + 1;
    }
}

在这里插入图片描述


http://lihuaxi.xjx100.cn/news/1021400.html

相关文章

【大数据之Hadoop】十三、MapReduce之WritableComparable排序

【大数据之Hadoop】十三、MapReduce之WritableComparable排序

MapReduce框架必须进行排序&#xff0c;MapTask和ReduceTask都会对key按字典顺序排序&#xff0c;是默认的行为&#xff08;默认使用快速排序&#xff09;&#xff0c;有利于提高效率。任何程序数据都会进行排序&#xff0c;不管逻辑是否需要。 对于排序而言分为两个阶段&#…
阅读更多...
响应式UI部件DevExtreme v22.2.5全新发布

响应式UI部件DevExtreme v22.2.5全新发布

DevExtreme拥有高性能的HTML5 / JavaScript小部件集合&#xff0c;使您可以利用现代Web开发堆栈&#xff08;包括React&#xff0c;Angular&#xff0c;ASP.NET Core&#xff0c;jQuery&#xff0c;Knockout等&#xff09;构建交互式的Web应用程序。从Angular和Reac&#xff0c…
阅读更多...
说走就走的旅行？你需要一个旅行必备清单

说走就走的旅行？你需要一个旅行必备清单

可能很多朋友都不用清单这个东西&#xff0c;更别说清单模版了。那清单真的好用吗&#xff1f;说实话&#xff0c;当你真的用清单来整理自己的日常工作&#xff0c;乃至生活琐事后&#xff0c;你就会发现你的时间多了&#xff0c;想要完成的事&#xff0c;大部分都可以按时完成…
阅读更多...
MZ深度解读SAP常见财务问题-02-账套在哪里？

MZ深度解读SAP常见财务问题-02-账套在哪里？

发文词&#xff1a;类似于新刊物的“发刊词”&#xff0c;我们也写两句发文词。笔者前些年关于SAP的文字主要包括“SAP那些事”系列文章中了&#xff0c;这些文章的视角主要是从顾问的角度进行描述的&#xff0c;侧重的也是系统功能和顾问职业的描述。 最近&#xff0c;笔者认…
阅读更多...
【网络应用开发】实验3——Web组件重用与JavaBeans

【网络应用开发】实验3——Web组件重用与JavaBeans

目录 Web组件重用与JavaBeans预习报告 一、实验目的 二、实验原理 三、实验预习内容 1. 静态include指令何时执行&#xff1f;主页面和被包含的子页面是否转换为一个转换单元&#xff1f; 2.动作指令何时执行&#xff1f;主页面和被包含的子页面是否转换为一个转换单元&a…
阅读更多...
PyTorch 之 基于经典网络架构训练图像分类模型

PyTorch 之 基于经典网络架构训练图像分类模型

文章目录一、 模块简单介绍1. 数据预处理部分2. 网络模块设置3. 网络模型保存与测试二、数据读取与预处理操作1. 制作数据源2. 读取标签对应的实际名字3. 展示数据三、模型构建与实现1. 加载 models 中提供的模型&#xff0c;并且直接用训练的好权重当做初始化参数2. 参考 pyto…
阅读更多...
【python设计模式】22、责任链模式

【python设计模式】22、责任链模式

责任链模式&#xff08;Chain of Responsibility Pattern&#xff09;是一种行为型设计模式&#xff0c;它允许多个对象都有机会处理请求&#xff0c;从而避免请求的发送者和接收者之间的耦合关系。这种模式建议让请求的发送者和接收者形成一条链&#xff0c;并沿着这条链传递请…
阅读更多...
【c语言】二维数组与指针 存储原理

【c语言】二维数组与指针 存储原理

创作不易&#xff0c;本篇文章如果帮助到了你&#xff0c;还请点赞支持一下♡>&#x16966;<)!! 主页专栏有更多知识&#xff0c;如有疑问欢迎大家指正讨论&#xff0c;共同进步&#xff01; 给大家跳段街舞感谢支持&#xff01;ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ…
阅读更多...
最新文章

Copyright @ 2022~2023