07数据结构与算法刷题之【树】篇

举报
长路 发表于 2022/11/22 23:28:51 2022/11/22
【摘要】 @[toc] 前言除了去年11月份以及今年近几月的算法刷题之外，只有在当时20年蓝桥杯准备的时候才刷过一些题，在当时就有接触到一些动归、递归回溯、贪心等等，不过那会也还是一知半解，做的题目也特别少，因为考虑到之后面试有算法题以及数据结构算法对于一个程序员十分重要，我也开始了刷题之路。我目前的学习数据结构与算法及刷题路径：1、学习数据结构的原理以及一些常见算法。2、代码随想录：跟着这个gith...

@[toc]

前言

除了去年11月份以及今年近几月的算法刷题之外，只有在当时20年蓝桥杯准备的时候才刷过一些题，在当时就有接触到一些动归、递归回溯、贪心等等，不过那会也还是一知半解，做的题目也特别少，因为考虑到之后面试有算法题以及数据结构算法对于一个程序员十分重要，我也开始了刷题之路。

我目前的学习数据结构与算法及刷题路径：

1、学习数据结构的原理以及一些常见算法。

2、代码随想录：跟着这个github算法刷题项目进行分类刷，在刷题前可以学习一下对应类别的知识点，而且这里面每道题都讲的很详细。

3、牛客网高频面试101题：牛客网—面试必刷101题，在刷的过程中可以在leetcode同步刷一下。

4、接下来就是力扣上的专栏《剑指offer II》、《程序员面试金典（第 6 版）》…有对应的精选题单来对着刷即可。

5、大部分的高频面试、算法题刷完后，就可以指定力扣分类专栏进行一下刷题了。

刚开始刷的时候真的是很痛苦的，想到去年一道题可能就需要好几小时，真的就很难受的，不过熬过来一切都会好起来，随着题量的增多，很多题目你看到就会知道使用什么数据结构或者算法来去求解，并且思考对应的时间空间复杂度，并寻求最优解，我们一起加油！

我的刷题历程

截止2022.8.18：

1、牛客网101题(其中1题是平台案例有问题)：image-20220818095030215

2、剑指offerII：image-20220818095104757

力扣总记录数：image-20220818095148897

加油加油！

二叉树基础知识点

1、二叉树的种类

满二叉树：只有度为0的结点和度为2的结点。

完全二叉树：除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h -1 个节点。

image-20211107165848019

二叉搜索树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树

image-20211107165921579

平衡二叉搜索树：AVL（Adelson-Velsky and Landis）树，是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

  • 红黑树就是一种二叉平衡搜索树。

image-20211107170014672

2、二叉树的存储方式

一般利于表示我们使用链式存储

顺序存储：数组存储。

  • 父节点的数组下表是i，那么它的左孩子就是i * 2 + 1，右孩子就是 i * 2 + 2

image-20211107170147507

链式存储：链表形式存储。

image-20211107170202397

3、二叉树的遍历方式

深度优先遍历：递归

  • 前序遍历（递归法，迭代法）
  • 中序遍历（递归法，迭代法）
  • 后序遍历（递归法，迭代法）

广度优先遍历

  • 层次遍历（迭代法）

4、二叉树节点定义

class TreeNode{
    private int val;
    private TreeNode left;
    private TreeNode right;
    
    public TreeNode(){
    }

    public TreeNode(int val){
        this.val = val;
    }

    public TreeNode(int val,TreeNode left, TreeNode right){
        this(val);
        this.left = left;
        this.right = right;
    }
}

剑指offer

剑指 Offer 54. 二叉搜索树的第k大节点【简单】

题目链接：剑指 Offer 54. 二叉搜索树的第k大节点

题目内容：给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

思路：二叉搜索树(左根右查询出来的是排序的)，找第k大的节点值。

1、右根左。然后使用一个变量来进行计数。

复杂度：

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
class Solution {
     
    public int kthLargest(TreeNode root, int k) {
        dfs(root, k);
        return val;
    }
    
    private int n;
    private int val;
    
    public void dfs(TreeNode root, int k) {
        if (root == null) {
            return;
        }
        dfs(root.right, k);
        n++;
        if (n == k) {
            val = root.val;
            return;
        }
        dfs(root.left, k);
    }
}

剑指 Offer 36. 二叉搜索树与双向链表【中等】

本题可在本章节牛客网-13题来进阶练习

题目链接：剑指 Offer 36. 二叉搜索树与双向链表

题目内容：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

思路：中序遍历(递归)+两个指针。

  • ps：与本章节中牛客网13有不同的就是首位指针需要进行连接。

image-20220712104543435

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }
    
    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    private Node head;
    private Node pre;

    public Node treeToDoublyList(Node root) {
        dfs(root);
        //dfs之后就是将尾部与首部连接起来
        if (head != null) {
            head.left = pre;
            pre.right = head;
        }
        return head;
    }
    
    public void dfs(Node root) {
        if (root == null) {
            return;
        }
        treeToDoublyList(root.left);
        //第一次情况or后面n次情况
        if (head == null) {
            head = root;
            pre = root;
        }else {
            pre.right = root;
            root.left = pre;
            pre = root;
        } 
        treeToDoublyList(root.right);
    }
}

剑指 Offer 32 - II. 从上到下打印二叉树 II【中等】

题目链接：剑指 Offer 32 - II. 从上到下打印二叉树 II

题目内容：从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

思路：

1、迭代遍历使用队列【通过】

复杂度分析：

  • 时间复杂度：O(n)，实际上2n
  • 空间复杂度：O(n)：一个是队列n、一个是list，实际上是3n。
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        //队列
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root);
        }
        while (!queue.isEmpty()) {
            List<Integer> nums = new ArrayList<>();
            List<TreeNode> list = new ArrayList<>();
            while (!queue.isEmpty()) {
                list.add(queue.poll());
            }
            for (TreeNode node: list) {
                nums.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            res.add(nums);
        }
        return res;
    }
}

2、递归，层数

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    private List<List<Integer>> res = new ArrayList<List<Integer>>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        dfs(root, 1);
        return res;
    }

    //k表示层数，node表示当前该层的结点
    public void dfs(TreeNode node, int k) {
        if (node != null) {
            if (res.size() < k) res.add(new ArrayList<Integer>());
            res.get(k - 1).add(node.val);
            dfs(node.left, k + 1);
            dfs(node.right, k + 1);
        }
    }

}

剑指 Offer 26. 树的子结构【中等】

题目链接：剑指 Offer 26. 树的子结构

题目内容：输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)。B是A的子结构， 即 A中有出现和B相同的结构和节点值。

思路：

1、dfs，遍历每个结点的同时，来对AB结点进行递归调用判定。

复杂度分析：时间复杂度O(MN)，空间复杂度O(M)，M，N谁的调用栈深，就是哪个。

class Solution {

    //该函数遍历每一个结点
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        //第一种写法：
        // if (A.val == B.val && helper(A.left, B.left) && helper(A.right, B.right)) {
        //     return true;
        // }
        //第二种写法：
        if (helper(A, B)) {
            return true;
        }
        return isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    
    //判断各自从当前结点开始是否一致，也就是说是否同是树的子结构
    public boolean helper(TreeNode A, TreeNode B) {
        //若是B当前为null，表示此时已经比较完毕
        if (B == null) {
            return true;
        }
        if (A == null) {
            return false;
        }
        //此时A、B都!=null
        if (A.val != B.val) {
            return false;
        }
        //只有左右相等才行
        return helper(A.left, B.left) && helper(A.right, B.right);
    }
}

剑指 Offer 33. 二叉搜索树的后序遍历序列【中等】

题目链接：剑指 Offer 33. 二叉搜索树的后序遍历序列

题目内容：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

思路：

1、构建二叉搜索树

复杂度分析：时间复杂度O(n)；空间复杂度O(n)

class Solution {

    private int end;
    
    //思路：以最后一个节点作为中间点，然后借助end坐标不断的去尝试在某个区间范围中看是否能够真的插入，例如[rootVal, max], [min, rootVal]
    public boolean verifyPostorder(int[] postorder) {
        this.end = postorder.length - 1;
        build(postorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
        return end < 0;
    }
    
    public void build(int[] postorder, int min, int max) {
        if (end < 0) { return; }
        //取得最后一个节点
        int rootVal = postorder[end];
        if (rootVal >= max || rootVal <= min) { return; }
        //只有符合条件，end才会-1表示该点是符合要求的
        end--;
        //接着尝试去挂载下一个节点
        build(postorder, rootVal, max);
        build(postorder, min, rootVal);
    }
}

剑指offer37. 序列化二叉树【困难，等同于牛客网的17】

题目链接： 序列化二叉树

牛客网

二叉树的前序、中序、后续遍历【简单】

题目：二叉树的前序遍历

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] preorderTraversal (TreeNode root) {
        List<Integer> list = new ArrayList();
        preorder(list, root);
        //返回的结果
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) 
            res[i] = list.get(i);
        return res;
    }
    
    //使用List集合来进行收集
    public void preorder(List<Integer> list, TreeNode root) {
        if (root == null) 
            return;
        list.add(root.val);
        preorder(list, root.left);
        preorder(list, root.right);
    }

}

对于中序，后序遍历只需要在preorder中改变下list.add的位置即可。

中序遍历（骚操作）

思路：利用栈，首先遍历添加所有左节点到栈中，接着出栈，记录值，接着结点变为右节点。

/**
 * 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<>();
        Stack<TreeNode> s = new Stack<>();
        TreeNode head = root;
        while (head != null || !s.isEmpty()) {
            while (head != null) {
                s.push(head);
                head = head.left;
            }
            TreeNode node = s.pop();
            res.add(node.val);
            head = node.right;
        }
        return res;
    }
}

二叉树的最大深度【简单】

题目链接：二叉树的最大深度

题目描述：求给定二叉树的最大深度，深度是指树的根节点到任一叶子节点路径上节点的数量。最大深度是所有叶子节点的深度的最大值。

思路1：通过递归来求出最大深度。

复杂度分析：

  • 时间复杂度：O(n)：遍历整个节点数。
  • 空间复杂度：O(n)：最坏情况下，二叉树化为链表，递归栈深度最大为n。

​```java
import java.util.*;

/*

  • public class TreeNode {
  • int val = 0;
  • TreeNode left = null;
  • TreeNode right = null;
  • }
    */

public class Solution {
/**
*
* @param root TreeNode类
* @return int整型
*/
public int maxDepth (TreeNode root) {
//最底层为0
if (root == null) {
return 0;
}
//取左右结点的最大层数
return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
}
}


## 二叉树中和为某一值的路径(一)【简单】

题目链接：[二叉树中和为某一值的路径(一)](https://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c?tpId=295&tqId=634&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj)

题目内容：给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。

**思路1**：采用递归来进行计算值。

复杂度分析：

+ 时间复杂度：O(n)。
+ 空间复杂度：O(n)。

```java
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    
    private boolean flag = false;
    
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        //若是当前结点为叶子结点
        if (root.left == null && root.right == null && sum - root.val == 0) {
            return true;
        }
        //递归左右结点
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
    
}

升级版：leetcode剑指 Offer 34. 二叉树中和为某一值的路径【中等】

题目地址：剑指 Offer 34. 二叉树中和为某一值的路径

题目内容：给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

  • 叶子节点 是指没有子节点的节点。

自己思路（不太行）：采用递归+回溯的思路来进行解决【自己想的】

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
/**
 * 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 {

    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        recursion(root, new ArrayList<Integer>(), target);
        return res;
    }

    public void recursion(TreeNode root, List<Integer> list, int target) {
        if (root == null) {
            return;
        }
        //若是叶子结点以及路径值为目标值
        if (root.left == null && root.right == null) {
            int index = list.size();
            list.add(index, root.val);
            if (isTargetNum(list, target)) {
                res.add(buildNewList(list));
            }
            list.remove(index);
            return;
        }
        int index = list.size();
        list.add(index, root.val);
        //递归
        recursion(root.left, list , target);
        //回溯
        list.remove(index);
        list.add(index, root.val);
        recursion(root.right, list, target);
        list.remove(index);
    }

    public boolean isTargetNum(List<Integer> list, int target) {
        if (list == null) {
            return false;
        }
        int sum = 0;
        for (int num : list) {
            sum += num;
        }
        return sum == target;
    }

    public List<Integer> buildNewList(List<Integer> list) {
        List<Integer> destList = new ArrayList<>();
        destList.addAll(list);
        return destList;
    }

}

思路1：dfs，通过递归来进行求解。

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
/**
 * 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 {
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    Deque<Integer> path = new LinkedList<Integer>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root, target);
        return ret;
    }

    public void dfs(TreeNode root, int target) {
        if (root == null) {
            return;
        }
        //填充该结点
        path.addLast(root.val);
        target -= root.val;
        //叶子结点满足的路径情况
        if (root.left == null && root.right == null && target == 0) {
            ret.add(new LinkedList<Integer>(path));
        }
        //递归调用
        dfs(root.left, target);
        dfs(root.right, target);
        //回溯
        path.removeLast();
    }

}

image-20220628215339305

对称的二叉树【简单】

学习：leetcode题解、 代码随想录—101. 对称二叉树

题目地址：对称的二叉树

题目内容：给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）

思路1：根左右 + 根右左来进行比对，思路依旧是使用递归方式来进行

import java.util.*;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public boolean recursion(TreeNode root1, TreeNode root2) {
        //最终符合情况
        if (root1 == null && root2 == null) {
            return true;
        }
        //中间比较差错情况
        if (root1 == null || root2 == null || root1.val != root2.val) {
            return false;
        }
        //左右子树对称比较
        return recursion(root1.left, root2.right) && recursion(root1.right, root2.left);
    }
    
    boolean isSymmetrical(TreeNode pRoot) {
        return recursion(pRoot, pRoot);
    }
}

2、迭代法

思路：其实与递归的思路大致相同，同样也是比较的左右节点(同外侧或内侧)，只不过这里会使用队列来进行临时存储要比对的两个左右节点，每次出队同时出队两个，入队时要入4个(每个节点都有左右孩子)。

//迭代法：使用队列
public boolean isSymmetric(TreeNode root) {
    Deque<TreeNode> queue = new LinkedList<>();
    if(root == null){
        return true;
    }
    queue.offer(root.left);
    queue.offer(root.right);
    while(!queue.isEmpty()){
        //每次出队2个元素
        TreeNode nodeLeft = queue.poll();
        TreeNode nodeRight = queue.poll();
        if(nodeLeft == null && nodeRight != null){
            return false;
        }else if(nodeLeft != null && nodeRight == null){
            return false;
        }else if(nodeLeft == null && nodeRight == null){
            continue;
        }else if(nodeLeft.val != nodeRight.val){
            return false;
        }

        //依次入队
        queue.offer(nodeLeft.left);
        queue.offer(nodeRight.right);
        queue.offer(nodeLeft.right);
        queue.offer(nodeRight.left);
    }
    return true;
}

image-20211108224529852

上面的是先入队，之后来进行统一判断的，后来我又写了一个在入队时进行判断的，写完后想了想实际上效果也不大，因为最多仅仅只是提前来对两对节点进行判断而已，这里的话就贴一下：

//迭代法：使用队列
public boolean isSymmetric(TreeNode root) {
    Deque<TreeNode> queue = new LinkedList<>();
    if(root == null || isNull(root.left,root.right)){
        return true;
    }
    if(!addQueue(root.left,root.right,queue)){
        return false;
    }

    while(!queue.isEmpty()){
        //每次出队2个元素
        TreeNode nodeLeft = queue.poll();
        TreeNode nodeRight = queue.poll();

        if(!isNull(nodeLeft.left,nodeRight.right)){
            if(!addQueue(nodeLeft.left,nodeRight.right,queue)){
                return false;
            }
        }
        if(!isNull(nodeLeft.right,nodeRight.left)){
            if(!addQueue(nodeLeft.right,nodeRight.left,queue)){
                return false;
            }
        }

    }
    return true;
}

public boolean addQueue(TreeNode node1,TreeNode node2,Deque queue){
    if(isSymmetry(node1,node2)){
        queue.offer(node1);
        queue.offer(node2);
        return true;
    }else{
        return false;
    }
}

public boolean isNull(TreeNode leftNode,TreeNode rightNode){
    return leftNode == null && rightNode == null;
}

/**
     * 判断是否对称
     * @param left
     * @param right
     * @return true表示允许将两个节点入队，false则表示不对称
     */
public boolean isSymmetry(TreeNode left,TreeNode right){
    if(left == null && right != null){
        return false;
    }else if(left != null && right == null) {
        return false;
    }else if(left.val == right.val){
        return true;
    }
    //        }else if(left == null && right == null){  //该判断要进行抽离
    //            return true;
    //        }
    return false;
}

image-20211108224431155

合并二叉树【简单】

题目链接：合并二叉树

题目内容：已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。

思路：采用递归构建左右子树的做法来进行合并二叉树，是通过进行前序遍历。

复杂度分析：

  • 时间复杂度：O(min(n, m))，m和n分别为两棵树的结点树，当一个树访问完时，自然就连接到了另一个数的节点
  • 空间复杂度：O(min(n, m))，递归栈的深度与访问时间也相同，只访问了小树的结点树。
public class Solution {
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        } 
        TreeNode node = new TreeNode(t1.val + t2.val);
        node.left = mergeTrees(t1.left, t2.left);
        node.right = mergeTrees(t1.right, t2.right);
        return node;
    }
    
}

判断是不是平衡二叉树【简单】

类似题：剑指 Offer 55 - II. 平衡二叉树

题目链接：判断是不是平衡二叉树

题目内容：输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

  • 平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

思路1：自顶向下

  • 每棵子树的左右子树都要去判断

复杂度分析：

  • 时间复杂度：O(n2)
  • 空间复杂度：O(n)
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        //平衡二叉树
        if (root == null) {
            return true;
        }
        int left = deep(root.left);
        int right = deep(root.right);
        if (left - right > 1 || left - right < -1) {
            return false;
        } 
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
    
    //求得该结点的最大结点深度
    public int deep(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = deep(node.left);
        int right = deep(node.right);
        return left > right ? left + 1 : right + 1;
    }
    
}

思路2：自底向上（最优解）

  • 直接从底部来进行比较高度来进行分析，然后不断的将结果向上传送。

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) {
            return true;
        }
        return getDeep(root) != -1;
    }
    
    //求得该结点的最大结点深度
    public int getDeep(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int left = getDeep(root.left);
        if (left < 0) {
            return -1;
        }
        int right = getDeep(root.right);
        if (right < 0) {
            return -1;
        }
        return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
    }
    
}

二叉搜索树的最近公共祖先【简单】

题目地址：二叉搜索树的最近公共祖先

题目内容：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

  • 二叉搜索树规律：二叉搜索树，左节点比父节点小，右节点比父节点大。

思路1：获取目标1、目标2的路径元素，然后比对遍历路径中的元素，最后相同的元素即为最近公共祖先。

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        //获取到两个结点的路径
        ArrayList<Integer> path1 = getPath(root, p);
        ArrayList<Integer> path2 = getPath(root, q);
        int res = -1;
        //比对路径元素
        for (int i = 0; i < path1.size() && i < path2.size(); i++) {
            int val1 = path1.get(i);
            int val2 = path2.get(i);
            if (val1 == val2) {
                res = val1;
            }else {
                break;
            }
        }
        return res;
    }
    
    //获取二叉搜索树指定结点的一个路径元素
    public ArrayList<Integer> getPath(TreeNode root, int target) {
        ArrayList<Integer> path = new ArrayList<Integer>();
        TreeNode cur = root;
        while (cur != null && cur.val != target) {
            path.add(cur.val);
            //当前结点>目标值
            if (cur.val > target) {
                cur = cur.left;
            }else{
                cur = cur.right;
            }
        }
        path.add(cur.val);
        return path;
    }
    
}

二叉树的镜像【简单】

题目地址：二叉树的镜像

题目内容：操作给定的二叉树，将其变换为源二叉树的镜像。

思路1：借助后序遍历，来进行左右节点交换。

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        if (pRoot == null) {
            return null;
        }
        //后序遍历
        TreeNode left = Mirror(pRoot.left);
        TreeNode right = Mirror(pRoot.right);
        pRoot.left = right;
        pRoot.right = left;
        return pRoot;
    }
}
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
二叉树 数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入