您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

查找类问题(2)_LC:144、94、145

1.1 树、树的遍历(LC:144 + 94 + 145)

根节点:每棵树只有一个根节点,如节点a

叶子节点:没有孩子的节点,如节点g、e、f

关于树的高度、深度、层:

树的分类:

  • 一般树:任意一个节点的子节点的个数都不受限制                   
  • 二叉树:二叉树是一个有序树(如一个父节点有两个子节点,A是左子节点,B是右子节点,结构顺序是A左B右,不能改变顺序,即节点是有序的) 
    • 关系:满二叉树是完全二叉树的特例,完全二叉树包含了满二叉树                                               
    • 完全二叉树:如果只是删除了满二叉树最底层最右边的连续若干个节点,这样形成的二叉树就是完全二叉树
    • 满二叉树:在不增加树的层数的前提下,无法再多添加一个节点的二叉树就是满二叉树(每一层的节点数都是最大的)
    • 一般二叉树:任意一个节点的子节点个数最多两个,且子节点的位置不可更改                                                              
    • 二叉树的优点:                                                      
      • 当得知一个树的节点个数,就会知道该树一共有几层
      • 已知完全二叉树中的任何一个节点,就可以查找该节点的父节点和子节点(也包括判断该节点有没有子节点)(采用连续的数组方式存储树的节点)
    • 二叉树的特点:
      • 一个有n个节点的二叉树,层数是m层,第m层最多有n/2个节点,第m-1层最多有(n/2)/2 = n/4个节点...

 

对二叉树的遍历操作(结合了递归的思想):                           

按照下面三种遍历方式,都可以将一个非线性的树转化成一个线性序列,进而存储在计算机的线性物理内存结构(如数组)中                           

先序遍历【先访问根节点】(根-左-右):遍历二叉树及二叉树中的子树时,第一个访问的节点一定是根节点

先访问根节点                                   

再先序访问左子树                                   

再先序访问右子树                           

中序遍历【中间访问根节点】(左-根-右)                                 

先中序遍历左子树                                    

再访问根节点                                    

再中序遍历右子树                           

后序遍历【最后访问根节点】(左-右-根):遍历二叉树及二叉树中的子树时,最后访问的节点一定是根节点

先后序遍历左子树                                    

再后序遍历右子树                                    

再访问根节点      

             

已知两种遍历序列求原始二叉树:

  • 只知道上面三种遍历序列中的任意一种,都不能把原始的二叉树还原出来               
  • 通过先序序列+中序序列或者中序序列+后序序列,都可以还原出原始二叉树,但是通过先序序列+后序序列是无法还原出原始的二叉树的                     
  • 换种说法:只有通过先序序列+中序序列或者中序序列+后序序列,才能唯一确定一个二叉树           

 

144. 二叉树的前序遍历 - 力扣(LeetCode) (leetcode-cn.com)

94. 二叉树的中序遍历 - 力扣(LeetCode) (leetcode-cn.com)

145. 二叉树的后序遍历 - 力扣(LeetCode) (leetcode-cn.com)

难度:中等

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

给你二叉树的根节点 root ,返回它节点值的 中序 遍历。

给你二叉树的根节点 root ,返回它节点值的 后序 遍历。

示例 1:

输入:root = [1,null,2,3]
前序输出:[1,2,3]
中序输出:[1,3,2]
后序输出:[3,2,1]

示例 2:

输入:root = []
前序输出:[]
中序输出:[]
后序输出:[]

示例 3:

输入:root = [1]
前序输出:[1]
中序输出:[1]
后序输出:[1]

示例 4:

输入:root = [1,2] 
前序输出:[1,2] 
中序输出:[2,1] 
后序输出:[2,1]

示例 5:

输入:root = [1,null,2] 
前序输出:[1,2] 
中序输出:[1,2] 
后序输出:[2,1]

 提示:

树中节点数目在范围 [0, 100] 内

-100 <= Node.val <= 100

思路:

解法1:递归

将每一个节点都看成其下面节点的根节点root,然后进行递归

解法2:迭代

思路和递归一致,只是手动实现了递归中的递归栈

一个细节点:

栈是遵循先入后出的,如果是先序遍历,则要入栈右节点,再入栈左节点,最后入栈根节点

代码:

解法1:递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
//前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        return traversal(root, list);
    }
    private List<Integer> traversal(TreeNode root, List<Integer> list){ //入递归时,每层递归的输入
        if(root == null){ //递归出口:递归终止条件
            return list;
        }
        list.add(root.val); //在每层递归中需要执行的操作
        //递归入口
        traversal(root.left,list); 
        traversal(root.right,list);
        return list; //每一层递归的返回值
    }
}

//中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        return traversal(root, list);
    }
    private List<Integer> traversal(TreeNode root, List<Integer> list){ //入递归时,每层递归的输入
        if(root == null){ //递归出口:递归终止条件
            return list;
        }
        //递归入口
        traversal(root.left,list);
        list.add(root.val); //在每层递归中需要执行的操作
        traversal(root.right,list);
        return list; //每一层递归的返回值
    }
}

//后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        return traversal(root, list);
    }
    private List<Integer> traversal(TreeNode root, List<Integer> list){ //入递归时,每层递归的输入
        if(root == null){ //递归出口:递归终止条件
            return list;
        }                
        //递归入口
        traversal(root.left,list); 
        traversal(root.right,list);
        list.add(root.val); //在每层递归中需要执行的操作
        return list; //每一层递归的返回值
    }
}

解法2:迭代

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
//先序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        
        //边界条件
        if(root == null){
            return list; 
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root); //出栈顺序:根-左-右,这里先入栈根节点,然后直接出栈根节点
        while(!stack.empty()){
            TreeNode node = stack.pop(); //将栈顶元素出栈,并返回元素值,注意这个node在每轮while中,都是充当根节点的身份
            list.add(node.val);
    	
     	 //先入栈每个根节点node的右节点,再入栈node的左节点,出栈顺序就能满足:左-右
            if(node.right != null){
                stack.push(node.right);
            }

            if(node.left != null){
                stack.push(node.left);
            }
        }
        return list;
    }
}

复杂度分析:

解法1:

  • 时间复杂度:O(n),其中 n 是二叉树的节点数。每一个节点恰好被遍历一次
  • 空间复杂度:O(n),为递归过程中递归栈的开销
    • 最坏情况下树呈现链状,为 O(n)(当n个节点成为链状时,二叉树的层数为n层,最深层的递归有n层递归嵌套,此时递归栈的空间复杂度为n)
    • 平均情况下为 O(logn)(即n个节点的二叉树的层数为logn时,最深层的递归有logn层递归嵌套,此时递归栈的空间复杂度为logn)

解法2:

  • 时间复杂度:O(n),其中 n 是二叉树的节点数。每一个节点恰好被遍历一次
  • 空间复杂度:O(n),为迭代过程中显式创建的栈的空间开销,平均情况下为 O(logn),最坏情况下树呈现链状,为 O(n)

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进