自学内容网 自学内容网
自学内容网 > 正文

【力扣热题100】—— Day8.二叉树的中序遍历

🕗 发布于 2024-12-10 02:30 算法  

要不停向上生长

                      —— 24.12.8 

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

二叉树的特性

1. 定义

二叉树是一种树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。

二叉树的子树有左右之分，次序不能颠倒。

2. 二叉树的类型

满二叉树（Full Binary Tree）：除叶子节点外，每个节点都有两个子节点。

完全二叉树（Complete Binary Tree）：所有层都是满的，除了最后一层，且最后一层的节点都集中在左边。

完美二叉树（Perfect Binary Tree）：所有内部节点都有两个子节点，并且所有叶子节点都在同一层。

二叉搜索树（Binary Search Tree, BST）：左子树上所有节点的值均小于根节点的值，右子树上所有节点的值均大于根节点的值。

平衡二叉树（Balanced Binary Tree）：任意节点的左右子树的高度差不超过1。

AVL树：一种自平衡二叉搜索树，通过旋转操作保持平衡。

堆（Heap）：完全二叉树，满足堆属性（最大堆或最小堆）。

3. 二叉树的遍历

前序遍历（Pre-order Traversal）：访问根节点 ——> 遍历左子树 ——> 遍历右子树。

中序遍历（In-order Traversal）：遍历左子树 ——> 访问根节点 ——> 遍历右子树。

后序遍历（Post-order Traversal）：遍历左子树 ——> 遍历右子树 ——> 访问根节点。

层序遍历（Level-order Traversal）：按照层次顺序从上到下、从左到右访问节点。

4. 二叉树的存储

链式存储：通过指针或引用连接节点，每个节点包含数据和指向左右子节点的指针。

顺序存储：使用数组存储二叉树，通常用于完全二叉树，通过计算下标来访问子节点。

5. 二叉树的应用

二叉搜索树（BST）：用于高效地进行插入、删除和查找操作。

堆：用于实现优先队列。

哈夫曼树（Huffman Tree）：用于数据压缩。

表达式树（Expression Tree）：用于表达式求值和转换。

6. 二叉树的算法

查找：查找特定值的节点。

插入：在二叉搜索树中插入新节点。

删除：从二叉搜索树中删除节点。

高度：计算二叉树的高度。

平衡性检查：检查二叉树是否是平衡二叉树。

7. 二叉树的实现

递归与非递归实现：遍历和操作二叉树时，可以使用递归或迭代方法。

方法一 递归

思路与方法

首先我们需要了解什么是二叉树的中序遍历：按照访问左子树--根节点--右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。

定义 MidTravel(root)表示当前遍历到 root 节点的答案，那么按照定义，我们只要递归调用 MidTravel(root.left)来遍历 root节点的左子树，然后将 root 节点的值加入答案，再递归调用 MidTravel(root.right)来遍历 root 节点的右子树即可，递归终止的条件为碰到空节点。

Python实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        self.MidTravle(root,res)
        return res
        
    def MidTravle(self,node, res):
        if not node:
            return
        self.MidTravle(node.left, res)
        res.append(node.val)
        self.MidTravle(node.right, res)

 Java实现

/**
 * 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> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        MidTravel(root, res);
        return res;
    }

    public void MidTravel(TreeNode node,List<Integer> res){
        if(node == null){
            return;
        }
        MidTravel(node.left, res);
        res.add(node.val);
        MidTravel(node.right, res);
    }
}

方法二 迭代

思路与方法

栈的基本操作

1.Push(压栈)：将元素添加到栈的顶部

2.Pop(出栈)：移除并返回栈顶的元素。

3.Peek(查看栈顶)：返回栈顶的元素，但不移除它。

4.lsEmpty(判断栈是否为空)：检查栈是否为空

5.size(获取栈的大小)：返回栈中元素的数量。

栈的特性

1.后进先出(LIFO)：最后进入栈的元素最先被移出。

2.线性结构：栈中的元素是线性排列的，每个元素只有一个后继元素(除了栈顶元素)3.操作受限:只能在栈顶进行插入和删除操作，不能在栈的中间或底部进行操作。

初始化一个空栈，当【根节点不为空】或者【栈不为空】时，从根节点开始遍历。若当前节点有左子树，则一直遍历左子树，每次将当前节点压入栈中，若当前节点无左子树，从栈中弹出该节点，尝试访问该节点的右子树。

Python实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        # 用p当做指针
        p = root
        while p or stack:
            # 把左子树压入栈中
            while p:
                stack.append(p)
                p = p.left
            # 输出 栈顶元素
            p = stack.pop()
            res.append(p.val)
            # 看右子树
            p = p.right
        return res

Java实现

/**
 * 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> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>(); 
        List<Integer> res = new ArrayList<Integer>();
        if(root == null){
            return res;
        }
        while(root != null || !stack.isEmpty()){
            if(root != null){
                stack.push(root);
                root = root.left;
            }else{
                TreeNode node = stack.pop();
                res.add(node.val);
                root = node.right;
            }
        }
        return res;
    }
}


原文地址：https://blog.csdn.net/m0_73983707/article/details/144316420

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024