首页 > 其他分享 >[代码随想录]Day13-二叉树part02

[代码随想录]Day13-二叉树part02

时间:2023-08-09 20:44:24浏览次数:52  
标签:Right TreeNode nil part02 随想录 二叉树 return root Left

题目:102. 二叉树的层序遍历

思路:

先把根放进去,然后每次都是左右就可以了。

记录一个深度,当len(res) == deepth的时候就说明这个深度还没有实例化,先搞一个再去收集。

代码:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

var res [][]int
func levelOrder(root *TreeNode) [][]int {
    res = [][]int{}
    level(root,0) // 根
    return res
}

func level(t *TreeNode,deepth int) {
    if t == nil { // 如果没有就返回
        return 
    }
    if len(res) == deepth {  // 实例化这一层
        res = append(res, []int{})
    }
    res[deepth] = append(res[deepth], t.Val) // 在这一层添加数据
    level(t.Left, deepth+1) // 遍历左节点
    level(t.Right, deepth+1) // 遍历右节点
}

参考:

代码随想录

题目:226. 翻转二叉树

思路:

二叉树的题递归分三步:

  1. 确定递归函数的参数和返回值
  2. 确定终止条件
  3. 确定单层递归的逻辑(前序、中序、后序、层序)

翻转二叉树,参数必然是树的指针,返回的结果是翻转后的二叉树同样也是一个树的指针。

当没有节点可以翻转了就结束。

这道题可以先把根翻转了,再去翻转左右节点可以;也可以先翻转左右节点再去翻转根,因此选择前序或者后序遍历。翻转就是把左右节点交换。可以尝试结合画图来理解。

代码:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
    if root == nil { // 空就不翻转
        return nil
    }
    root.Left, root.Right = root.Right, root.Left
    invertTree(root.Left)
    invertTree(root.Right)

    return root
}

参考:

代码随想录

题目:101. 对称二叉树

思路:

二叉树的题递归分三步:

  1. 确定递归函数的参数和返回值
  2. 确定终止条件
  3. 确定单层递归的逻辑(前序、中序、后序、层序)

这题是需要两个子树同时进行的,想要判断对称:

  1. 左子树的左侧 = 右子树的右侧 ,即外侧相同
  2. 左子树的右侧 = 右子树的左侧 ,即内侧相同

那么参数就是一个左子树一个右子树,返回结果为true 或者 false。

终止条件是出现false:

  1. 左子树nil,右子树不为nil
  2. 左子树不为nil,右子树nil
  3. 左子树不为nil,右子树不为nil,但是左子树不等于右子树

以及true的条件:左子树 = 右子树 = nil (左子树 = 右子树 ≠ nil的情况是继续向下递归因此不是终止条件)

本题只能是后序遍历,因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等

20210203144624414.png

代码:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return compare(root.Left, root.Right)
}

func compare(left, right *TreeNode) bool {
    if left != nil && right == nil {
        return false
    }else if left == nil && right != nil {
        return false
    }else if left == nil && right == nil {
        return true
    }else if left.Val != right.Val {
        return false
    }
    outside := compare(left.Left,  right.Right) // 外侧是不是相同
    inside := compare(left.Right, right.Left)  // 内侧是不是相同
    root := outside && inside // 根节点根据内外侧是否相同来决定是true还是false
    return root
}

参考:

代码随想录

标签:Right,TreeNode,nil,part02,随想录,二叉树,return,root,Left
From: https://www.cnblogs.com/wtcsky/p/17617964.html

相关文章

  • 二叉树后序遍历非递归遍历实现图解
    二叉树的后序遍历输入:{1,#,2,3}返回值:[3,2,1]输入:{1}返回值:[1]代码实现publicint[]postorderTraversal(TreeNoderoot){TreeNodecur=root;List<Integer>list=newArrayList<>();Deque<TreeNode>stack=newArrayDeq......
  • 144. 二叉树的前序遍历
    给你二叉树的根节点 root ,返回它节点值的 前序 遍历。示例1:输入:root=[1,null,2,3]输出:[1,2,3]示例2:输入:root=[]输出:[]示例3:输入:root=[1]输出:[1]示例4:输入:root=[1,2]输出:[1,2]classSolution:defpreorderTraversal(self,root:Optional[TreeNode])->Li......
  • 145. 二叉树的后序遍历
    给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。示例1:输入:root=[1,null,2,3]输出:[3,2,1]示例2:输入:root=[]输出:[]classSolution:defpostorderTraversal(self,root:Optional[TreeNode])->List[int]:res=[]defdfs(node):......
  • 剑指 Offer 28. 对称的二叉树(简单)
    题目:classSolution{public:booltraversal(TreeNode*left,TreeNode*right){//递归判断左右两个**镜像**节点if(left==nullptr&&right!=nullptr)returnfalse;elseif(left!=nullptr&&right==nullptr)returnfalse;el......
  • [代码随想录]Day12-二叉树part01
    今天的题目就是二叉树的前中后序遍历,目前只写了递归方法,之后再补迭代方法。题目:144.二叉树的前序遍历思路:前序遍历:根-左-右代码1:递归,递归情况下只需要改变递归的顺序即可实现前中后序遍历。/***Definitionforabinarytreenode.*typeTreeNodestruct{*Va......
  • 代码随想录算法训练营第十三天| 239. 滑动窗口最大值 347.前 K 个高频元素 总结
    239.滑动窗口最大值 (一刷至少需要理解思路)    卡哥建议:之前讲的都是栈的应用,这次该是队列的应用了。本题算比较有难度的,需要自己去构造单调队列,建议先看视频来理解。    题目链接/文章讲解/视频讲解:https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%......
  • 剑指 Offer 32 - III. 从上到下打印二叉树 III(中等)
    题目:解法一:classSolution{public:voidtraversal(TreeNode*cur,vector<vector<int>>&result,intdepth){if(cur==nullptr)return;if(result.size()==depth)result.push_back(vector<int>());result[depth].pu......
  • [代码随想录]Day11-栈与队列part03
    题目:239.滑动窗口最大值思路:说实话这题真不能说是困难题,麻烦是麻烦点但是比较容易实现。维护一个单调队列,队列内是由大到小排序(数组内的顺序是由小到大的),每次移动都会进行两次判断:如果前面去掉的数就是队列的首部,那么就要把首部移除如果后面添加的数比队尾的元素要大就......
  • 代码随想录算法训练营第十一天| 20. 有效的括号 1047. 删除字符串中的所有相邻重复项
    20.有效的括号    卡哥建议:讲完了栈实现队列,队列实现栈,接下来就是栈的经典应用了。 大家先自己思考一下 有哪些不匹配的场景,在看视频 我讲的都有哪些场景,落实到代码其实就容易很多了。   题目链接/文章讲解/视频讲解:https://programmercarl.com/0020.%E6%9C%8......
  • 王道408--数据结构--用数组实现二叉树--并查集及其优化代码
    一、数组实现二叉树(下标从0开始)#include<stdio.h>typedefstruct_TreeNode{intdata;boolIsEmpty;//结点是否为空//因为我们的二叉树不一定是满二叉树,中间可能有一些节点不存在//值为1代表空}TreeNode;//初始化voidInitTreeNode(TreeNodet[......