代码编织梦想

算法练习-二叉树

1 二叉树的基础知识

1.1 二叉树的存储

1.1.1 基于指针的存储方式

public class BinartTree {
	public class Node { // 节点的定义
        public int data;
        public Node left;
        public Node right;
    }
    private Node root = null;
}

1.1.2基于数组的存储方式

用数组来存储所有的节点。根节点存储在下标为1的位置

节点之间的父子关系,通过数组下表计算得到:如果节点x的下标是i

——下标为 i*2 的位置存储左子节点

——下标为 2*i+1 的位置存储右子节点

——下标为 i / 2 的位置存储就是父节点

这种存储方式基本只适用于完全二叉树,因为非完全二叉树会产生很多的空洞。

1.2 二叉树的遍历

1.2.1 前序遍历

先打印根节点,然后再先序遍历左子树,最后先序遍历右子树

public void preOrder(Node root) {
    if (root == null) return;
    System.out.println(root.data);
    preOrder(root.left);
    preOrder(root.right);
}

1.2.2 中序遍历

先中序遍历左子树,再打印根节点,最后中序遍历右子树

public void inOrder(Node root) {
	if (root == null) return;
	inOrder(root.left);
    System.out.println(root.data);
    inOrder(root.right);
}

1.2.3 后序遍历

先后序遍历左子树,再后序遍历右子树,最后打印根节点

public void postOrder(Node root) {
    if (root == null) return;
    postOrder(root.left);
    postOrder(root.right);
    System.out.println(root.data);
}

1.3 二叉查找树

二叉查找树是一种特殊的二叉树,支持快速查找、插入、删除数据

对于二叉查找树中任意一个节点,其左子树中每个节点的值,都小于这个节点的值。其右子树每个节点的值,都大于这个节点的值

1.3.1 二叉查找树的实现

  • 递归实现
public class Node {
    private int data;
    private Node left;
    private Node right;
    public Node(int data) {
        this.data = data;
    }
}

private Node root = null;

public Node find_r(Node root, int data) {
    if (root == null) return null;
    if (root.data == data) return root;
    if (data < root.data) {
        return find_r(root.left, data);
    } else {
        return find_r(root.right, data);
    }
}
  • 非递归实现
public Node find(Node root, int data) {
    Node p = root;
    while (p != null) {
        if (data < p.data) {
            p = p.left;
        } else if (data > p.data) {
            p = p.right;
        } else {
            return p;
        }
    }
    return null;
}

1.3.2 二叉查找树的插入

如果要插入的数比当前节点的值小,且当前节点的左子树为空,则将新数据插入到左子节点的位置,如果左子树不为空,再递归遍历左子树,找到插入位置

如果要插入的数比当前节点的值大,且当前节点的右子树为空,则将新数据插入到右子节点的位置,如果右子树不为空,再递归遍历右子树,找到插入位置

  • 递归实现
if (root == null) {
    root = new Node(data);
    return;
}

public void insert_r(Node root, int data) {
    if (data > root.data) {
        if (root.right == null) {
            root.right = new Node(data);
        } else {
            insert_r(root.right, data);
        }
    } else {
        if (root.left == null) {
            root.left = new Node(data);
        } else {
            insert_r(root.left, data);
        }
    }
}
  • 非递归实现
public void insert(int data) {
	if (root == null) {
        root = new Node(data);
        return;
    }
    
    Node p = root;
    while(p != null) {
        if(data > p.data) {
            if (p.right == null) {
		    	p.right = new Node(data);
                 return;
            }
            p = p.right;
        } else {
            if (p.left == null) {
                p.left = new Node(data);
                return;
            }
            p = p.left;
        }
    }
}

1.3.3 二叉查找树的删除操作

针对待删除的节点的子节点的个数不同,分三种情况处理

  1. 要删除的节点没有子节点。直接将父节点中指向要删除的节点的指针设置为null即可
  2. 要删除的节点只有一个子节点。更新父节点中指向要删除的节点的指针,让他重新指向要删除节点的子节点
  3. 要删除的节点有两个子节点。需要找到这个节点的右子树中的最小节点,把他替换到要删除的节点上(或者左子树的最大节点,总之是最接近这个被删除节点值的节点)。然后再删除掉这个最小节点,因为最小节点肯定没有左子节点,然后用上面两条规则删除这个最小节点
public void delete(int data) {
    Node p = root; // p指向要删除的节点,初始化指向根节点
    Node pp = null; // pp指向的是p的父节点
    while(p != null && p.data != data) { // 查找要删除的节点及其父节点
        pp = p;
        if (data > p.data) p = p.right;
        else p = p.left;
    }
    if (p == null) return; // 没找到
    
    // 要删除的节点有两个子节点
    if(p.left != null && p.right != null) { // 查找右子树的最小节点
    	Node minP = p.right;
        Node minPP = p; // minPP表示minP的父节点
        while (minP.left != null) {
			minPP = minP;
            minP = minP.left;
        }
        p.data = minP.data;
        p = minP;
        pp = minPP;
    }
    
    // 删除节点是叶子节点或者只有一个子节点
    Node child = null;
    if (p.left != null) child = p.left;
    else if (p.right != null) child = p.right;
    
    if (pp == null) root = child; // 删除的是根节点
    else if (pp.left == p) pp.left = child;
    else pp.right = child;
}

2 二叉树相关题型

2.1 二叉树前中后序遍历

2.1.1 N叉树的前序遍历

链接:https://leetcode.cn/problems/n-ary-tree-preorder-traversal

给定一个 n 叉树的根节点 root ,返回 其节点值的 前序遍历 。

n 叉树 在输入中按层序遍历进行序列化表示,每组子节点由空值 null 分隔(请参见示例)。

示例 1:

输入:root = [1,null,3,2,4,null,5,6]
输出:[1,3,5,6,2,4]
示例 2:

输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出:[1,2,3,6,7,11,14,4,8,12,5,9,13,10]

提示:

节点总数在范围 [0, 104]内
0 <= Node.val <= 104
n 叉树的高度小于或等于 1000

进阶:递归法很简单,你可以使用迭代法完成此题吗?

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> preorder(Node root) {
        preorder_r(root);
        return result;
    }
    public void preorder_r(Node root) {
        if (root == null) return;
        result.add(root.val);
        for (int i = 0; i < root.children.size(); i++) {
            preorder_r(root.children.get(i));
        }
    }
}

2.1.2 N叉树的后序遍历

链接:https://leetcode.cn/problems/n-ary-tree-postorder-traversal

给定一个 n 叉树的根节点 root ,返回 其节点值的 后序遍历 。

n 叉树 在输入中按层序遍历进行序列化表示,每组子节点由空值 null 分隔(请参见示例)。

示例 1:

请添加图片描述

输入:root = [1,null,3,2,4,null,5,6]
输出:[5,6,3,2,4,1]
示例 2:

请添加图片描述

输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出:[2,6,14,11,7,3,12,8,4,13,9,10,5,1]

提示:

节点总数在范围 [0, 104] 内
0 <= Node.val <= 104
n 叉树的高度小于或等于 1000

进阶:递归法很简单,你可以使用迭代法完成此题吗?

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> postorder(Node root) {
        postorder_r(root);
        return result;
    }
    public void postorder_r(Node root) {
        if (root == null) return;
        
        for (int i = 0; i < root.children.size(); i++) {
            postorder_r(root.children.get(i));
        }
        result.add(root.val);
    }
}

2.2 二叉树按层遍历

2.2.1 从上到下打印二叉树

链接:https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof

从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回:

[3,9,20,15,7]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        if (root == null) return new int[0];
        List<Integer> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            result.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        int[] resultArray = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            resultArray[i] = result.get(i);
        }
        return resultArray;
    }
}

2.3 二叉树上的递归

2.3.1 二叉树的最大深度

链接:https://leetcode.cn/problems/maximum-depth-of-binary-tree

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

/**
 * 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 int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

2.3.2 平衡二叉树

链接:https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof

输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

返回 false 。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private boolean balanced = true;
    
    public boolean isBalanced(TreeNode root) {
        height(root);
        return balanced;
    }
    
    private int height(TreeNode root) {
        if (root == null) return 0;
        if (balanced == false) return 0;
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (Math.abs(leftHeight - rightHeight) > 1) {
            balanced = false;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

2.4 二叉查找树

2.4.1 二叉搜索树的第k大节点

链接:https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof

给定一棵二叉搜索树,请找出其中第 k 大的节点的值。

示例 1:

输入: root = [3,1,4,null,2], k = 1
3
/
1 4

2
输出: 4
示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/
3 6
/
2 4
/
1
输出: 4

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int count = 0;
    int result;
    public int kthLargest(TreeNode root, int k) {
        inorder(root, k);
        return result;
    }
    
    private void inorder(TreeNode root, int k) {
        if (count >= k) return;
        if (root == null) return;
        inorder(root.right, k);
        count++;
        if (count == k) {
            result = root.val;
            return;
        }
        inorder(root.left, k);
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_62759952/article/details/129650756

数据结构与算法练习-二叉树-爱代码爱编程

深度优先遍历二叉树 描述 使用递归可以轻易的遍历一颗二叉树,根据访问顺序的不同分为 先序遍历 中-左-右中序遍历 左-中-右后序遍历 左-右-中 代码 /** * 深度优先 先序遍历 *

试解leetcode算法题--二叉树的后序遍历_bubblecode的博客-爱代码爱编程

<题目表述> 给定一个二叉树,返回它的 后序 遍历。 示例: 输入: [1,null,2,3] 1 \ 2 / 3 输出: [3,2,1] 进阶: 递归算法很简单,你可以通过迭代算

算法刻意练习-LeetCode实战21-二叉树的最大深度(C++)-爱代码爱编程

题目:二叉树的最大深度 原题链接:二叉树的最大深度 这道题使用使用BFS(广度优先遍历),将每个节点的数据域用来记录当前节点的深度即可。代码如下: /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left;

算法刻意练习-LeetCode实战22-二叉树的中序遍历(C++)-爱代码爱编程

题目:二叉树的中序遍历 原题链接:二叉树的中序遍历 递归就好,代码如下: /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNo

树与算法----二叉树的实现-爱代码爱编程

树 树与树算法树的概念树的术语树的种类树的存储与表示链式存储常见的一些树的应用场景二叉树二叉树的基本概念二叉树的性质(特性)二叉树的节点表示以及树的创建二叉树的遍历深度优先遍历广度优先遍历(层次遍历)二叉树实现的完整代码 树与树算法 树的概念 树(英语:tree)是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树

算法练习-二叉树展开为链表-爱代码爱编程

114. 二叉树展开为链表 思路代码 给定一个二叉树,原地将它展开为一个单链表。 例如,给定二叉树 1 / \ 2 5 / \ \ 3 4 6 将其展开为: 1 \ 2 \ 3 \ 4 \ 5 \

数据结构与算法-二叉树-爱代码爱编程

二叉树 树的基本概念有序树,无序树,森林二叉树二叉树的性质真二叉树(Proper Binnary Tree)满二叉树(Full Binary Tree)完全二叉树(Complete Binary Tree)完全二叉树的性质二叉树的遍历练习利用前序遍历树状打印二叉树翻转二叉树计算二叉树的高度判断一棵树是否为完全二叉树前驱节点(predecessor)

数据结构与算法练习-二叉树中序遍历-爱代码爱编程

python数据结构与算法练习-二叉树中序遍历 二叉树中序遍历思路python实现 二叉树中序遍历 链接: link. 给定一个二叉树的根节点 root ,返回它的 中序 遍历。 样例 输入:root = [1,null,2,3] 输出:[1,3,2] 输入:root = [] 输出:[] 输入:root = [1,2] 输出:[

python数据结构与算法练习-二叉树层序遍历-爱代码爱编程

python数据结构与算法练习-二叉树层序遍历问题 层序遍历python实现 层序遍历 二叉树的层序遍历是从树的每一层开始从左到右挨个访问树的节点。这里采用队列的思想,先将根节点入队列,然后出队并查看当前节点是否存在左孩子和右孩子,如果存在,则递归调用。 python实现 from collections import deque def

JAVA练习78-二叉树中和为某一值的路径-爱代码爱编程

给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1: 输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出:[[5,4,11,2],[5,8

算法练习-leetcode hot 100 543. 二叉树的直径_yinyl03的博客-爱代码爱编程

今日心情:为了offer冲冲冲! 题目描述: LeetCode Hot 100 543. 二叉树的直径 给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。   解题代码: /** * Definition for a binary tree node.

算法练习-leetcode hot 100 617. 合并二叉树_yinyl03的博客-爱代码爱编程

今日心情:为了offer冲冲冲! 题目描述: LeetCode Hot 100 617. 合并二叉树 给你两棵二叉树: root1 和 root2 。 想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后

算法练习-leedcode 剑指 offer 55 - ii. 平衡二叉树_yinyl03的博客-爱代码爱编程

今日心情:不知道该说些什么麻了 题目描述: LeedCode 剑指 Offer 55 - II. 平衡二叉树 输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。 解题代码: /** * Definition for a binary tree node.

算法练习- leetcode 剑指 offer 07. 重建二叉树_yinyl03的博客-爱代码爱编程

今日心情:无语言表 题目描述:  LeetCode 剑指 Offer 07. 重建二叉树 输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 解题代码: /** * Definition for a binary tree node. * publi

数据结构与算法----详解二叉树的遍历(迭代、递归)_小鱼干儿♛的博客-爱代码爱编程

文章目录 实现二叉树的类前序遍历中序遍历后序遍历层次遍历总结 ❤️ 作者简介:大家好我是小鱼干儿♛是一个热爱编程、热爱算法的大三学生,蓝桥杯国赛二等奖获得者🐟 个人主页 :https://blog.c

2022/11/20 算法练习-二叉树的中序遍历_圈西的博客-爱代码爱编程

题目介绍 给定一个二叉树的根节点,返回它的中序遍历。 示例1: 输入如上图 输出:[1,3,2] 示例2: 输入:[] 输出:[] 思路 首先介绍一下中序遍历: 这里1是根结点,2是1的右孩子结点,3是2的左孩子结

算法练习day17|110 平衡二叉树、257 二叉树的所有路径、404 左叶子之和-爱代码爱编程

110 平衡二叉树 110 平衡二叉树 一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1(高度:从叶子节点开始往上数的最大节点数量)如果某子树不是平衡二叉树则违反了定义,返回-1,这会

数据结构与算法-爱代码爱编程

认识二叉树 递归实现先序中序后序 class Node<V>{ V value; Node left; Node right; } 根据递归序得出, 先序:第一次到达时就打印,不是第一次什么也不做 中序:

数据结构-爱代码爱编程

二叉树的前中后序遍历: 所谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二叉树中的节点进行相应的操作,并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历 是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础。 按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历: 1. 前序遍历(P