前端算法:树(力扣144、94、145、100、104题)

目录

一、树(Tree)

1.介绍

2.特点

3.基本术语

4.种类

二、树之操作

1.遍历

前序遍历(Pre-order Traversal):访问根节点 -> 遍历左子树 -> 遍历右子树。

中序遍历(In-order Traversal):遍历左子树 -> 访问根节点 -> 遍历右子树(用于 BST 时可得到排序结果)。

后序遍历(Post-order Traversal):遍历左子树 -> 遍历右子树 -> 访问根节点。

层序遍历(Level-order Traversal):逐层访问树的节点,通常使用队列实现。

2.插入和删除

3.查找

三、树的力扣算法实战

1.144. 二叉树的前序遍历

2.94. 二叉树的中序遍历

 3.145. 二叉树的后序遍历

4.100. 相同的树

5.104. 二叉树的最大深度


一、树(Tree)

1.介绍

树(Tree)是一种重要的数据结构,广泛应用于计算机科学中。它由节点组成,并且有一个根节点,其他节点通过边连接形成层级关系。

2.特点

  1. 层级关系:树结构是分层的,根节点位于顶层,每个节点可以有多个子节点。
  2. 无环性:树中不存在环,即从一个节点出发不可能回到该节点。
  3. 节点的子节点:每个节点可以有零个或多个子节点。

3.基本术语

  • 根节点:树的顶层节点。
  • 叶子节点:没有子节点的节点。
  • 子节点:某个节点直接连接的下层节点。
  • 兄弟节点:同一父节点的子节点。
  • 高度:树的高度是从根节点到最深叶子节点的最长路径的边数。
  • 4.种类

    1. 树(Tree):一般的树结构,没有特定的限制。

    2. 二叉树(Binary Tree):每个节点最多有两个子节点。

    3. 完全二叉树(Complete Binary Tree):除了最后一层外,其他层的节点都填满,最后一层的节点尽量向左排列。
    4. 满二叉树(Full Binary Tree):每个节点要么是叶子节点,要么有两个子节点。
    5. 非完全二叉树(Incomplete Binary Tree):不是完全二叉树的任意形式。
    6. 二叉搜索树(Binary Search Tree, BST):一种特殊的二叉树,左子树的所有节点值小于根节点,右子树的所有节点值大于根节点。

    7. 自平衡树(Self-balancing Tree):如 AVL 树和红黑树,保持树的高度平衡以优化查找效率。

    8. N 叉树(N-ary Tree):每个节点可以有 N 个子节点的树结构。

    9. Trie(前缀树):一种用于存储字符串的树,常用于快速查找和前缀匹配。

    二、树之操作

    1.遍历

    前序遍历(Pre-order Traversal):访问根节点 -> 遍历左子树 -> 遍历右子树。
        // 前序遍历
        preOrderTraversal(node) {
            if (node) {
                console.log(node.value);
                this.preOrderTraversal(node.left);
                this.preOrderTraversal(node.right);
            }
        }
    中序遍历(In-order Traversal):遍历左子树 -> 访问根节点 -> 遍历右子树(用于 BST 时可得到排序结果)。
        // 中序遍历
        inOrderTraversal(node) {
            if (node) {
                this.inOrderTraversal(node.left);
                console.log(node.value);
                this.inOrderTraversal(node.right);
            }
        }
    后序遍历(Post-order Traversal):遍历左子树 -> 遍历右子树 -> 访问根节点。
    
        // 后序遍历
        postOrderTraversal(node) {
            if (node) {
                this.postOrderTraversal(node.left);
                this.postOrderTraversal(node.right);
                console.log(node.value);
            }
        }
    
    层序遍历(Level-order Traversal):逐层访问树的节点,通常使用队列实现。
        // 层序遍历
        levelOrderTraversal() {
            if (!this.root) return;
    
            const queue = [this.root];
            while (queue.length > 0) {
                const node = queue.shift();
                console.log(node.value);
                if (node.left) queue.push(node.left);
                if (node.right) queue.push(node.right);
            }
        }

    2.插入和删除

    插入:在二叉搜索树中,插入新节点时需要找到合适的位置,保证 BST 的性质。

        // 插入
        insert(value) {
            const newNode = new TreeNode(value);
            if (this.root === null) {
                this.root = newNode;
                return;
            }
            this.insertNode(this.root, newNode);
        }
    
        insertNode(node, newNode) {
            if (newNode.value < node.value) {
                if (node.left === null) {
                    node.left = newNode;
                } else {
                    this.insertNode(node.left, newNode);
                }
            } else {
                if (node.right === null) {
                    node.right = newNode;
                } else {
                    this.insertNode(node.right, newNode);
                }
            }
        }

    删除:删除节点时可能需要重新调整树结构,以保持树的性质,尤其在 BST 中。

        // 删除
        delete(value) {
            this.root = this.deleteNode(this.root, value);
        }
    
        deleteNode(node, value) {
            if (node === null) {
                return null;
            }
            if (value < node.value) {
                node.left = this.deleteNode(node.left, value);
            } else if (value > node.value) {
                node.right = this.deleteNode(node.right, value);
            } else {
                // 找到要删除的节点
                if (node.left === null && node.right === null) {
                    return null; // 无子节点
                }
                if (node.left === null) {
                    return node.right; // 只有右子节点
                }
                if (node.right === null) {
                    return node.left; // 只有左子节点
                }
                // 找到右子树中的最小节点
                const minNode = this.findMinNode(node.right);
                node.value = minNode.value; // 替换值
                node.right = this.deleteNode(node.right, minNode.value); // 删除最小节点
            }
            return node;
        }

    3.查找

    在树中查找节点的过程依赖于树的性质。对于二叉搜索树,可以通过比较节点值快速找到目标节点。

        search(value) {
            return this.searchNode(this.root, value);
        }
    
        searchNode(node, value) {
            if (node === null) {
                return false;
            }
            if (value === node.value) {
                return true;
            }
            return value < node.value
                ? this.searchNode(node.left, value)
                : this.searchNode(node.right, value);
        }

    三、树的力扣算法实战

    1.144. 二叉树的前序遍历

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

    示例 1:

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

    输出:[1,2,3]

    示例 2:

    输入:root = [1,2,3,4,5,null,8,null,null,6,7,9]

    输出:[1,2,4,5,6,7,3,8,9]

    示例 3:

    输入:root = []

    输出:[]

    示例 4:

    输入:root = [1]

    输出:[1]

    解题思路:将二叉树进行先序遍历(中左右:根节点->左子树->右子树)

    代码:

    var preorderTraversal = function(root) {
        const arr = []
    
        const fun = (node) =>{
            if(node){
                arr.push(node.val)
                    fun(node.left)
                    fun(node.right)
            }
            
        }
    
        fun(root)
        return arr
    };

    2.94. 二叉树的中序遍历

    题目描述:给定一个二叉树的根节点 root ,返回 它的 中序 遍历

    示例 1:

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

    示例 2:

    输入:root = []
    输出:[]
    

    示例 3:

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

    解题思路:将二叉树进行中序遍历(左中右:左子树->根节点->右子树)

    代码:

    var inorderTraversal = function(root) {
        const arr = []
        const fun = (root) =>{
            if(!root) return
            fun(root.left)
            arr.push(root.val)
            fun(root.right)
        }
        fun(root)
        return arr
    };

     3.145. 二叉树的后序遍历

    题目描述:给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历

    示例 1:

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

    输出:[3,2,1]

    示例 2:

    输入:root = [1,2,3,4,5,null,8,null,null,6,7,9]

    输出:[4,6,7,5,2,9,8,3,1]

    示例 3:

    输入:root = []

    输出:[]

    示例 4:

    输入:root = [1]

    输出:[1]

    解题思路:将二叉树进行中序遍历(左右中:左子树->右子树->根节点)

    代码:

    var postorderTraversal = function(root) {
        const arr = []
        const fun = (root) =>{
            if(!root) return
            fun(root.left)
            fun(root.right)
            arr.push(root.val)
        }
        fun(root)
        return arr
    };
    
    

    4.100. 相同的树

    题目描述:

    给你两棵二叉树的根节点 pq ,编写一个函数来检验这两棵树是否相同。

    如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

    示例 1:

    输入:p = [1,2,3], q = [1,2,3]
    输出:true
    

    示例 2:

    输入:p = [1,2], q = [1,null,2]
    输出:false
    

    示例 3:

    输入:p = [1,2,1], q = [1,1,2]
    输出:false
    

     解题思路:首先判断两个节点是否都为空,是则返回true;如果一个为空一个不为空,则返回false,再判断两个节点的val值是否相同,不同返回false,依次进行传入两棵树的左节点和右节点

    代码:

    var isSameTree = function(p, q) {
        if(p === null && q === null) return true;
        if(p === null || q === null) return false
        if(p.val !== q.val) return false
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right)
    };

    5.104. 二叉树的最大深度

    题目描述:

    给定一个二叉树 root ,返回其最大深度。

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

    示例 1:

    输入:root = [3,9,20,null,null,15,7]
    输出:3
    

    示例 2:

    输入:root = [1,null,2]
    输出:2
    

    解题思路: 首先判断树是否为空,空则返回0,将树放入栈中,以栈的长度为值进行遍历,将栈的长度定义一个值len,每循环一次计数器num+1,len–,依次弹出stack的栈中元素,判断是否有左右子节点,在将其压入栈中,最后返回num值

    代码

    var maxDepth = function(root) {
        if(!root) return 0
        const stack = [root]
        let num = 0
        while(stack.length){
            let len = stack.length
            num++
            while(len--){
                const o = stack.shift()
                o.left && stack.push(o.left)
                o.right && stack.push(o.right)
            }
        }
        return num
    };

    作者:码农白衣

    物联沃分享整理
    物联沃-IOTWORD物联网 » 前端算法:树(力扣144、94、145、100、104题)

    发表回复