• 树的常见面试题

    树的常见面试题

    1 树的后继节点

    node的后继节点指的是中序遍历树之后，排在node后面一个节点

    1.1 题型一：求二插搜索树的后继节点（后继者）

    题目链接:https://leetcode.cn/problems/successor-lcci/

    在这里插入图片描述
    思路：

    利用二叉搜索树特性：根节点的值大于左子树，根节点的值小于右子树

    首先，如果要寻找的p节点的右子树不为null
    ①p.right != null
    直接找p右子树的最左节点，更新successor的值

    if(p.right != null){
    //p的右子树不为null -> p的右子树的最左节点
    TreeNode node = p.right;
    while(node.left != null){
        node = node.left;
    }
    successor = node;
} 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    ②p.right == null
    通用代码：

    TreeNode node = root;
while(node != null){
	if(p.val < node.val){
		successor = node;
		node = node.left;
	}else{
		//如果p节点在root的先左后右或先右后左，会返回null
		//如果在一直左或一直右，返回其parent
		node = node.right;
	} 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    详细分析：

    p的右子树为null，判断p节点在root节点的左边还是右边
    1）如果p在root节点左边：
    一直向下找，找到p节点的父节点，
    如果是"左右"(root节点左子树的右子树，先左后右)：直接返回父节点的父节点
    如果是"左左":直接返回父节点

    TreeNode node = root;
while(node != null){
	if(p.val < node.val){
		successor = node;
		node = node.left;
	}else{
		//如果p节点在root的先左后右或先右后左，会返回null
		//如果在一直左或一直右，返回其parent
		node = node.right;
	} 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    2）如果p在root节点的右边:
    如果是"右左"（root节点的右子树的左子树）：直接返回parent
    如果是"右右":直接返回null

    TreeNode node = root;
while(node != null){
	if(p.val < node.val){
		successor = node;
		node = node.left;
	}else {
		node = node.right;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    全部代码：

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode successor = null;
        if(p.right != null){
            //p的右子树不为null -> p的右子树的最左节点
            TreeNode node = p.right;
            while(node.left != null){
                node = node.left;
            }
            successor = node;
        } 
        //p的右子树为null
        TreeNode node = root;
        while(node != null){
            if(p.val < node.val){
                //node往左
                successor = node;
                node = node.left;
            } else {
                //p的值大于node的值
                node = node.right;
            }
        }
        return successor;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    1.2 题型二：node节点多一个属性parent【指向其父亲】

    Node结构：

    public static class Node{
    private int value;
    private Node left;
    private Node right;
    private Node parent;

    public Node(int value){
        this.value = value;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    分两种情况：一种node的right为null，一种node的right不为null
    思路：
    ①node.right != null

    找到node节点右子树的最左节点【中序：左中右】

    //找到最左边节点
public static Node getLeftMost(Node node){
    if(node == null){
        return node;
    }
    while(node.left != null){
        node = node.left;
    }
    return node;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    ②node.right == null

    判断node是parent的左子树还是右子树：
    如果是左子树，直接返回parent；
    如果是右子树，让parent往上找【如果node为root的最右节点，while循环之后会返回null】

    Node parent = node.parent;
while(parent != null && parent.right == node){ //当前节点是其父亲节点的右孩子【null】
    node = parent;
    parent = node.parent;
}
//当前节点是其父亲的左孩子
return parent;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    全部代码：

    public static class Node{
     private int value;
     private Node left;
     private Node right;
     private Node parent;

     public Node(int value){
         this.value = value;
     }
 }

 public static Node getSuccessorNode(Node node){
     if(node == null){
         return null;
     }
     if(node.right != null){
         //node节点的右子树不为null,找到右子树的最左边节点
         return getLeftMost(node.right);
     } else { //无右子树【node：1.左孩子  2.右孩子 】
         Node parent = node.parent;
         while(parent != null && parent.right == node){ //当前节点是其父亲节点的右孩子【null】
             node = parent;
             parent = node.parent;
         }
         //当前节点是其父亲的左孩子
         return parent;
     }
 }
 //找到最左边节点
 public static Node getLeftMost(Node node){
     if(node == null){
         return node;
     }
     while(node.left != null){
         node = node.left;
     }
     return node;
 }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    2 验证类题目

    2.1 判断树是否为完全二叉树或满二叉树

    2.1.1 是否是完全二叉树

    完全二叉树是指除最后一层以外，其他层全满，且最后一层叶子节点排布必须是从左到右

    先介绍解法二：【通过递归】
    思路：创建信息收集类，根据树的递归最后返回结果
    ①信息收集类Info

    //创建信息收集类
 public static class Info {
     //是否是完全二叉树
     public boolean isCBT;
     //是否是满二叉树
     public boolean isFull;
     public int height;

     public Info(boolean isCBT, boolean isFull, int height) {
         this.isCBT = isCBT;
         this.isFull = isFull;
         this.height = height;
     }
 }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    ②调用process方法返回结果

    public static boolean isCBT2(Node head) {
    if (head == null) {
        return true;
    }
    return process(head).isCBT;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    ③处理方法process的编写

    //处理类
public static Info process(Node node) {
    if (node == null) {
        //base case:跳出递归
        return new Info(true, true, 0);
    }
    Info leftInfo = process(node.left);
    Info rightInfo = process(node.right);
    //处理高度[+1：本层高度]
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    //判断是否是满二叉树：左右是否是满，左右高度是否相等
    boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
    //判断是否是完全二叉树：①左右树都为满     ②左子树为满 右子树为完全  ③左子树为完全 右子树为满
    boolean isCBT = false;
    if (isFull) {
        //为满二叉树的树一定是完全二叉树
        isCBT = true;
    } else {
        if (leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height) {
            isCBT = true;
        }
        if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
            isCBT = true;
        }
        if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
            //左为满，右下面为null
            isCBT = true;
        }
    }
    return new Info(isCBT, isFull, height);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    解法二的全代码：

    //创建信息收集类
public static class Info {
    //是否是完全二叉树
    public boolean isCBT;
    //是否是满二叉树
    public boolean isFull;
    public int height;

    public Info(boolean isCBT, boolean isFull, int height) {
        this.isCBT = isCBT;
        this.isFull = isFull;
        this.height = height;
    }
}

public static boolean isCBT2(Node head) {
    if (head == null) {
        return true;
    }
    return process(head).isCBT;
}

//处理类
public static Info process(Node node) {
    if (node == null) {
        //base case:跳出递归
        return new Info(true, true, 0);
    }
    Info leftInfo = process(node.left);
    Info rightInfo = process(node.right);
    //处理高度[+1：本层高度]
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    //判断是否是满二叉树：左右是否是满，左右高度是否相等
    boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
    //判断是否是完全二叉树：①左右树都为满     ②左子树为满 右子树为完全  ③左子树为完全 右子树为满
    boolean isCBT = false;
    if (isFull) {
        //为满二叉树的树一定是完全二叉树
        isCBT = true;
    } else {
        if (leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height) {
            isCBT = true;
        }
        if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
            isCBT = true;
        }
        if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
            //左为满，右下面为null
            isCBT = true;
        }
    }
    

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52

    解法一：【通过队列依次来判断】

    //使用队列
public static boolean isCBT1(Node head) {
    if (head == null) {
        return true;
    }
    LinkedList<Node> queue = new LinkedList<>();
    //是否遇到过左右两个孩子不双全的节点[叶子节点]
    boolean leaf = false;
    Node l = null;
    Node r = null;
    queue.add(head);
    while (!queue.isEmpty()) {
        head = queue.poll();
        l = head.left;
        r = head.right;
        if (leaf && (r != null || l != null) || (l == null && r != null)) {
            //遇到了不双全的节点，发现当前节点不是叶节点
            return false;
        }
        if (l != null) {
            queue.add(l);
        }
        if (r != null) {
            queue.add(r);
        }
        if (l == null || r == null) {
            leaf = true;
        }
    }
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    最后，通过对数器验证解法二是否正确
    全代码：

    
import java.util.LinkedList;

//判断是否是完全二叉树或满二叉树
public class CBTOrFullDemo {

    //创建节点类
    public static class Node {
        private int value;
        private Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    //使用队列
    public static boolean isCBT1(Node head) {
        if (head == null) {
            return true;
        }
        LinkedList<Node> queue = new LinkedList<>();
        //是否遇到过左右两个孩子不双全的节点[叶子节点]
        boolean leaf = false;
        Node l = null;
        Node r = null;
        queue.add(head);
        while (!queue.isEmpty()) {
            head = queue.poll();
            l = head.left;
            r = head.right;
            if (leaf && (r != null || l != null) || (l == null && r != null)) {
                //遇到了不双全的节点，发现当前节点不是叶节点
                return false;
            }
            if (l != null) {
                queue.add(l);
            }
            if (r != null) {
                queue.add(r);
            }
            if (l == null || r == null) {
                leaf = true;
            }
        }
        return true;
    }

    //创建信息收集类
    public static class Info {
        //是否是完全二叉树
        public boolean isCBT;
        //是否是满二叉树
        public boolean isFull;
        public int height;

        public Info(boolean isCBT, boolean isFull, int height) {
            this.isCBT = isCBT;
            this.isFull = isFull;
            this.height = height;
        }
    }

    public static boolean isCBT2(Node head) {
        if (head == null) {
            return true;
        }
        return process(head).isCBT;
    }

    //处理类
    public static Info process(Node node) {
        if (node == null) {
            //base case:跳出递归
            return new Info(true, true, 0);
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        //处理高度[+1：本层高度]
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        //判断是否是满二叉树：左右是否是满，左右高度是否相等
        boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
        //判断是否是完全二叉树：①左右树都为满     ②左子树为满 右子树为完全  ③左子树为完全 右子树为满
        boolean isCBT = false;
        if (isFull) {
            //为满二叉树的树一定是完全二叉树
            isCBT = true;
        } else {
            if (leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height) {
                isCBT = true;
            }
            if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
                isCBT = true;
            }
            if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
                //左为满，右下面为null
                isCBT = true;
            }
        }
        return new Info(isCBT, isFull, height);
    }

    //定义对数器进行测试
    //for test
    public static Node generateTree(int maxLevel, int maxValue) {
        //从第1层开始
        return generate(1, maxLevel, maxValue);
    }

    //for test
    public static Node generate(int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        Node head = new Node((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }

    public static void main(String[] args) {
        int maxLevel = 6;
        int maxValue = 100;
        int times = 100_0000;
        for(int i = 0; i < times; i++){
            Node node = generateTree(maxLevel, maxValue);
            if(isCBT1(node) != isCBT2(node)){
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    2.1.2 是否是满二叉树

    同上，同是否是完全二叉树一样，只需要返回isFull信息即可【递归方法】

  • 相关阅读:
    Go错误处理方式真的不好吗？
    【vue3源码】二、vue3的响应系统分析
    浅谈城市轨道交通视频监控与AI视频智能分析解决方案
    基于JavaWeb（SSM框架）的网上书店的设计与实现
    [实践篇]13.7 来自QNX侧的dump
    当出现“无法成功完成操作，因为文件包含病毒或潜在的垃圾软件“时的解决办法
    asp毕业设计——基于asp+sqlserver的电子论坛系统设计与实现（毕业论文+程序源码）——电子论坛系统
    C语言实现猜数字游戏！（图解超级简单。）
    数据结构篇——KMP算法
    MySQL数据库的日志管理
  • 原文地址：https://blog.csdn.net/weixin_45565886/article/details/126407237