treenode:104. 二叉树的最大深度(LeetCode 题解)

 2021-07-08 14:27    77  

题目描述treenode:给定一个二叉树,找出其最大深度。

treenode:104. 二叉树的最大深度(LeetCode 题解)

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

treenode:104. 二叉树的最大深度(LeetCode 题解)

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

treenode:104. 二叉树的最大深度(LeetCode 题解)

示例:

treenode:104. 二叉树的最大深度(LeetCode 题解)

给定二叉树 [3,9,20,null,null,15,7],

treenode:104. 二叉树的最大深度(LeetCode 题解)

返回它的最大深度 3 。

树的定义

首先,给出我们将要使用的树的结点 TreeNode 的定义。

方法一、递归:算法

直观的方法是通过递归来解决问题。在这里,我们演示了 DFS(深度优先搜索)策略的示例。

复杂度分析

时间复杂度:我们每个结点只访问一次,因此时间复杂度为 O(N), 其中 N 是结点的数量。空间复杂度:在最糟糕的情况下,树是完全不平衡的,例如每个结点只剩下左子结点,递归将会被调用 N 次(树的高度),因此保持调用栈的存储将是 O(N)。但在最好的情况下(树是完全平衡的),树的高度将是 log⁡(N)。因此,在这种情况下的空间复杂度将是 O(log⁡(N))。

方法二、迭代:我们还可以在栈的帮助下将上面的递归转换为迭代。

我们的想法是使用 DFS 策略访问每个结点,同时在每次访问时更新最大深度。所以我们从包含根结点且相应深度为 1 的栈开始。然后我们继续迭代:将当前结点弹出栈并推入子结点。每一步都会更新深度。

复杂度分析

时间复杂度:O(N)。空间复杂度:O(N)。

Leetcode98. 验证二叉搜索树

给定一个二叉树,判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征:

节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。示例 1:

输入: 2 / \ 1 3输出: true示例 2:

输入: 5 / \ 1 4 / \ 3 6输出: false解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ,但是其右子节点值为 4 。解答:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { /** //方法一:根据性质:BST(二叉搜索树)的中序遍历是有序的(从小到大的) public boolean isValidBST(TreeNode root) { //创建一个ArrayList用来保存该二叉搜索树的全部节点 ArrayList<Integer> list = new ArrayList<>(); //中序遍历该二叉树,把节点的值都放入ArrayList中 help(list, root); //验证ArrayList中的元素是否是由小到大的顺序,如果不是直接返回false for(int i = 0; i < list.size() - 1; i++){ if(list.get(i) >= list.get(i + 1)){ return false; } } //如果ArrayList中的元素是由小到大的顺序,则返回true return true; } //本函数实现的功能就是二叉树的中序遍历,并将节点的值存进ArrayList中去 public void help(ArrayList list, TreeNode root){ if(root == null) return; help(list, root.left); list.add(root.val); help(list, root.right); } **/ //方法二:使用迭代: public boolean isValidBST(TreeNode root) { return helper(root, null, null); } public boolean helper(TreeNode root, Integer min, Integer max){ if(root == null) return true; //左孩子的取值范围在负无穷到root.val之间;右孩子的取值范围在root.val到正无穷之间 if(min != null && root.val <= min) return false; if(max != null && root.val >= max) return false; return helper(root.left, min, root.val) & helper(root.right, root.val, max); }}

本文标签:哪些Spring核心嵌套循环详解

原文链接:https://www.xgfox.com/alpx/642.html

本文版权:如无特别标注,本站文章均为原创。