day17 二叉树part04

2024-01-16 13:44
文章标签 二叉树 part04 day17

本文主要是介绍day17 二叉树part04,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

110. 平衡二叉树

简单
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

class Solution {public boolean isBalanced(TreeNode root) {return (getHeight(root) == -1) ? false : true; }public int getHeight(TreeNode node){//遇到空节点了为终止,返回0,表示当前节点为根节点的树高度为0if (node == null) {return 0;} // 如果左右子树返回了-1 说明已经有子树不是平衡二叉树了,继续返回-1int leftHeight = getHeight(node.left);if (leftHeight == -1) return -1;int rightHeight = getHeight(node.right);if (rightHeight == -1) return -1;// 左右子树高度差大于1,return -1表示已经不是平衡树了int diff = Math.abs(leftHeight - rightHeight)if (diff > 1) return -1;// 由子节点的高度计算当前节点的高度int height = Math.max(leftHeight, rightHeight) + 1;return height;}
}

257. 二叉树的所有路径

简单
给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。

难点1:要想顺序记录从根节点到叶子节点的路径,就需要从上到下访问,所以这个题只能用前序遍历。

难点2:第一次遇到回溯的题目,要懂得回溯的原理和思想。

在这里插入图片描述

class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> res = new ArrayList<>(); // 存放最终结果if (root == null) {return res;}List<Integer> path = new ArrayList<>(); // 存放最终结果中的单独一条路径traversal(root, path, res);return res;}public void traversal(TreeNode node, List<Integer> path, List<String> res) {path.add(node.val); //前序遍历,先加入中间节点if (node.left == null && node.right == null) { // 如果当前这个节点就是一个叶子节点,就把当前这条路径加入res中StringBuilder sb = new StringBuilder(); //StringBuilder拼接更方便for (int i = 0; i < path.size() - 1; i++) {sb.append(path.get(i)); // 这里不是sb.add,是appendsb.append("->");}sb.append(path.get(path.size() - 1)); //最后一个节点后面没有"->",所以单独处理res.add(sb.toString()); //收集这个路径return; //到这个节点就停了,后面不需要处理了,可以退出了,这里没有删除当前path的最后一个节点值的原因是,当前函数结束后,会在它的上个递归里删除}// 递归和回溯是同时进行,所以要放在同一个花括号里if (node.left != null) { //如果左节点不为空,把左节点送去继续递归traversal(node.left, path, res);path.remove(path.size() - 1); //!!!回溯,这一步是最难理解的,这一句代表着,把path中的路径再回退一步,回退这一步永远是站在当前节点,去取回当前节点的左或右节点,就好像往筒里放乒乓球,放进去了要拿出来}if (node.right != null) {traversal(node.right, path, res);path.remove(path.size() - 1);}}
}

其实不用回溯也能做(或许是回溯了,但是回溯得不明显,递归一定伴随着回溯)(回溯可以理解为从某一节点出发然后又回到该节点),来看下力扣精选的题解代码:

// 每个节点访问的时候先把他存储起来,到叶子结点的时候再添加到集合中,最后返回集合的值public List<String> binaryTreePaths(TreeNode root) {List<String> res = new ArrayList<>();dfs(root, "", res);return res;}private void dfs(TreeNode root, String path, List<String> res) {//如果为空,直接返回if (root == null)return;//如果是叶子节点,说明找到了一条路径,把它加入到res中if (root.left == null && root.right == null) {res.add(path + root.val);return;}//如果不是叶子节点,在分别遍历他的左右子节点dfs(root.left, path + root.val + "->", res);dfs(root.right, path + root.val + "->", res);}作者:数据结构和算法
链接:https://leetcode.cn/problems/binary-tree-paths/solutions/400434/257-er-cha-shu-de-suo-you-lu-jing-tu-wen-jie-xi-by/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

404. 左叶子之和

简单
给定二叉树的根节点 root ,返回所有左叶子之和。

难点:左叶子之和一定是等于左子树的左叶子之和加上右子树的左叶子之和的。这是这里能用递归的根本逻辑。

递归:当遇到左叶子节点的时候,记录数值,然后通过递归求取左子树左叶子之和,和 右子树左叶子之和,相加便是整个树的左叶子之和。
层次:这个题层次遍历法也能做,因为层次遍历能访问到所有的节点,对所有的节点都判断一次: if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) 然后加上值就行,也不复杂。
这里我们写一下递归法:
建议多默写几遍这个题的递归法,我觉得有好处

class Solution {public int sumOfLeftLeaves(TreeNode root) {return postOrder(root);}public int postOrder(TreeNode node) {if (node == null) {return 0;}int sumLeft;int sumRight;// 如果当前节点的左节点就是一个叶子节点,那么记录下它的值if (node.left != null && node.left.left == null && node.left.right == null) {sumLeft = node.left.val;} else {// 如果当前节点的左节点不是一个叶子节点(要么是空节点,要么下面还有很多节点),那么就继续递归sumLeft = postOrder(node.left);}// 右节点也放入递归计算它的左叶子sumRight = postOrder(node.right);return sumLeft + sumRight;}
}

这篇关于day17 二叉树part04的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/612783

相关文章

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

在二叉树中找到两个节点的最近公共祖先(基于Java)

如题  题解 public int lowestCommonAncestor(TreeNode root, int o1, int o2) {//记录遍历到的每个节点的父节点。Map<Integer, Integer> parent = new HashMap<>();Queue<TreeNode> queue = new LinkedList<>();parent.put(roo

数据结构--二叉树(C语言实现,超详细!!!)

文章目录 二叉树的概念代码实现二叉树的定义创建一棵树并初始化组装二叉树前序遍历中序遍历后序遍历计算树的结点个数求二叉树第K层的结点个数求二叉树高度查找X所在的结点查找指定节点在不在完整代码 二叉树的概念 二叉树(Binary Tree)是数据结构中一种非常重要的树形结构,它的特点是每个节点最多有两个子节点,通常称为左子节点和右子节点。这种结构使得二叉树在数据存储和查找等方面具

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机(二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机(二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用,那个马的关系,后面就注意,dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ

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

(写给未来遗忘的自己) 题目: 代码: class Solution {public:int countNodes(TreeNode* root) {queue<TreeNode*>node_que;if(root==nullptr) return 0;node_que.push(root);int result;while(!node_que.empty()){int layer_s

代码随想录 -- 二叉树 -- 平衡二叉树

110. 平衡二叉树 - 力扣(LeetCode) 思路:仍然是递归调用 1. 定义一个递归函数 count 用来计算二叉树的层数 2. isBalanced 函数:如果传入根节点为空返回真;如果根节点 | 左子树的层数 - 右子树的层数 | 大于1,返回假;最后返回根节点左子树、右子树是否是平衡二叉树。 class Solution(object):def count(self,root

【数据结构】你真的学会了二叉树了吗,来做一做二叉树的算法题及选择题

文章目录 1. 二叉树算法题1.1 单值二叉树1.2 相同的树1.3 另一棵树的子树1.4 二叉树的遍历1.5 二叉树的构建及遍历 2. 二叉树选择题3. 结语 1. 二叉树算法题 1.1 单值二叉树 https://leetcode.cn/problems/univalued-binary-tree/description/ 1.2 相同的树 https://leet

二叉树的层次遍历(10道)

(写给未来遗忘的自己) 102.二叉数的层序遍历(从上到下) 题目: 代码: class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; queue<TreeNode*> node; if (root == nullptr) {

求二叉树的深度——(力扣c语言)

题目如下: 给定一个二叉树 root ,返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1: 输入:root = [3,9,20,null,null,15,7]输出:3 示例 2: 输入:root = [1,null,2]输出:2 题目解析: 上题就是要利用递归对目标进行访问找到叶子节点之后记录并返回到根节点之后对左右两个