首页 > 其他分享 >代码随想录第14天|二叉树的递归遍历

代码随想录第14天|二叉树的递归遍历

时间:2024-03-20 22:59:11浏览次数:30  
标签:preorder 遍历 14 List 随想录 result root 二叉树

二叉树的理论基础

代码随想录 (programmercarl.com)

关于二叉树,你该了解这些!| 二叉树理论基础一网打尽,二叉树的种类、二叉树的存储方式、二叉树节点定义、二叉树的遍历顺序_哔哩哔哩_bilibili

二叉搜索树:二叉搜索树是一个有序树。左子树不为空,则左子树上所有节点的值均小于根节点的值;右子树不为空,则右子树上所有结点的值均大于根节点的值

二叉树的存储方式

二叉树可以用链表存储,也可以用数组存储。详细解答

二叉树的递归遍历

代码随想录 (programmercarl.com)

每次写递归都要靠直觉? 这次带你学透二叉树的递归遍历!| LeetCode:144.前序遍历,145.后序遍历,94.中序遍历_哔哩哔哩_bilibili

递归三部曲:

1、确定递归的参数和返回值

2、确定终止条件

3、确定单层递归的逻辑

前序遍历为例:

1、递归的参数和返回值: 因为要打印出遍历后的节点的数值,需要传入TreeNode来存放节点的数值;返回类型为空

class Solution{
    public List<Integer> preorderTraversal(TreeNode root){
    List<Integer> result = new ArrayList<Integer>();
    preorder(root,result);
    return result;
    }

    public void preorder(TreeNode root, List<Integer> result){

    }
}

2、终止条件:节点为空

if(root == null) {
    return;
}

3、单层递归的逻辑:先取中间节点,然后才是左、右

result.add(root.val);
preorder(root.left,result);
preorder(root.right,result);

综合代码:

class Solution{
    public List<Integer> preorderTraversal(TreeNode root){
    List<Integer> result = new ArrayList<Integer>();
    preorder(root,result);
    return result;
    }

    public void preorder(TreeNode root, List<Integer> result){
        if(root == null) {
            return;
        }
        result.add(root.val);
        preorder(root.left,result);
        preorder(root.right,result);
    }
}

中序遍历和后序遍历是一样的,不过在3、单层递归逻辑中,语句的顺序发生了改变:

中序遍历:

class Solution{
    public List<Integer> inorderTraversal(TreeNode root){
    List<Integer> result = new ArrayList<Integer>();
    preorder(root,result);
    return result;
    }

    public void preorder(TreeNode root, List<Integer> result){
        if(root == null) {
            return;
        }
        preorder(root.left,result);
        result.add(root.val);
        preorder(root.right,result);
    }
}

后序遍历:

class Solution{
    public List<Integer> postorderTraversal(TreeNode root){
    List<Integer> result = new ArrayList<Integer>();
    preorder(root,result);
    return result;
    }

    public void preorder(TreeNode root, List<Integer> result){
        if(root == null) {
            return;
        }
        preorder(root.left,result);
        preorder(root.right,result);
        result.add(root.val);
    }
}

标签:preorder,遍历,14,List,随想录,result,root,二叉树
From: https://blog.csdn.net/lilith_2001/article/details/136831848

相关文章

  • The 14th Jilin Provincial Collegiate Programming Contest
    The14thJilinProvincialCollegiateProgrammingContest-Codeforces队友太猛了,我整场就只写了D,其他题给队友开完了,预计补一下M,FProblemD.Trie(AC自动机+树状数组)大概就是给定一颗Trie树操作一是给Trie树的fail树上一个集合中的点的所有子节点打上一个......
  • 复试C++14真题 看程序写结果5 虚函数、继承 易错?
    复试C++14真题 看程序写结果5  虚函数、继承#include<iostream>usingnamespacestd;classA{public:virtualvoidprint(){cout<<"A::print"<<endl;}//voidprint(){cout<<"A::print"<<endl;}};classB:public......
  • 蓝桥杯- 第14届模拟题第二套
     老规矩,先看外设要求......ADC,LED,LCD,KEY,EEPROM。除了EEPROM之外其它没什么新意,所以我们来看看EEPROM就可以了(其它可以在第一套模拟题中看到) /*****************************************************************************************************************/EE......
  • 01天【代码随想录算法训练营34期】 第一章 数组part01 (704. 二分查找、 27. 移除元
    二分查找classSolution(object):defsearch(self,nums,target):low=0high=len(nums)-1while(low<=high):mid=(high+low)//2ifnums[mid]==target:returnmide......
  • 【代码随想录】广度优先搜索
    思路分析先前已经做过一道深度优先搜索了,可以看出,DFS比较适合求两点之间的所有路径这样的问题,因为其路径都是逐条求出的,而BFS则可能一下子求出多条路径,适合用来求最短路径。关于BFS的过程前面已经学习过很多次了,遍历到一个节点时要先保存其所有邻接节点再继续向下遍历,一般是使......
  • 代码随想录刷题记录第一天 | 数组 | 704. 二分查找,27. 移除元素
    题目链接:704.二分查找-https://leetcode.cn/problems/binary-search/description/27.移除元素-https://leetcode.cn/problems/remove-element/description/文章学习链接:https://programmercarl.com/数组理论基础.html视频学习链接:https://www.bilibili.com/video/BV1f......
  • P1142 轰炸
    原题链接题解由于本题数据范围小,所以考虑暴力两点确定一条直线,所以我们先确定两个点AB,然后再遍历所有点C,如果向量AB叉乘AC等于0代表共线(没说从哪里起飞)code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;structnode{llx,y;}a[1000];intmain......
  • 代码随想录算法训练营第十三天|239. 滑动窗口最大值、347.前 K 个高频元素、总结
    题目:239.滑动窗口最大值文章链接:代码随想录视频链接:LeetCode:239.滑动窗口最大值题目链接:力扣题目链接图释:classSolution{public://自己定义一个优先队列classMyQueue{public: deque<int>deq; //弹出 voidpop(intvalue){ //当输入的数组与队顶......
  • 代码随想录算法训练营第十一天| 20. 有效的括号、1047. 删除字符串中的所有相邻重复项
    题目:20.有效的括号文章链接:代码随想录视频链接:LeetCode:20.有效的括号题目链接:力扣题目链接图释:classSolution{public://有效的括号boolisValid(strings){ //遇到左括号时就放入右括号,遇到右括号时,与栈内的顶元素进行比较 //情况一:与栈顶元素相等,则是t......
  • ceph:在centos7 上通过 ceph-ansible 安装ceph 14
    安装本质上就是熟悉ceph-ansible工具的各种配置关系:哪些时必须的?默认值来自哪里?各种配置分散在哪些配置文件内?...../site.yml./group_vars/all.yml  ./group_vars/其他各种组件特定的.yml  注意:all.yml里的配置很大部分时依赖于site.yml的配置的。根据需要进行配置。 ......