树【LeetCode】

前言

写作于
2022-11-04 17:24:02

发布于
2022-11-20 16:01:08

树简单

创建树

TreeNode

package data.tree;

/**
 * @author CSDN@日星月云
 * @date 2022/10/28 00:25
 */
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode() {
        //无参数构造函数
    }
    public TreeNode(int val) {
        this.val = val;
    }
    public TreeNode(int val,TreeNode left,TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }


    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }


}

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

BiTree

package data.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author CSDN@日星月云
 * @date 2022/11/1 17:51
 */
public class BiTree {
    public TreeNode root;
    public BiTree(){
        root=null;
    }
    //用扩展先序遍历序列创建二叉链表
    //依靠队列，当队首元素分配了左右孩子就出队
    public TreeNode setTree(Integer[] data)//data为传入的形参数组，如Integer[] nums = {1,2,null,4,null,5}
    {
        root = new TreeNode(data[0]);
        Queue<TreeNode> queue = new LinkedList<>();//先入先出，构造子树
        queue.offer(root);
        int i = 1;//从第二个元素开始入列
        while(i<data.length)
        {
            TreeNode node = queue.poll();//弹出队列中的树节点
            if(data[i] != null)//当实参的元素不为null时，添加左节点
            {
                node.left = new TreeNode(data[i]);
                queue.offer(node.left);
            }
            i++;//不管实参(传入Integer[] data的Integer数组)的元素是不是null，均需要后移一位
            if(data[i] != null)//当实参的元素不为null时，添加右节点
            {
                node.right = new TreeNode(data[i]);
                queue.offer(node.right);
            }
            i++;
        }
        return root;//返回根节点
    }


    //访问
    void visit(int n){
        System.out.print(n+" ");
    }

    // 递归 先序
    void preOrder(TreeNode root){
        //先序遍历二叉树，root为根节点的指针
        if (root!=null){
            visit(root.val);
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    //层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> list=new ArrayList<>();
            int count=queue.size();
            for (int i = 0; i<count ; i++) {
                TreeNode p = queue.poll();
                list.add(p.val);
                if (p.left != null) {
                    queue.add(p.left);
                }
                if (p.right != null) {
                    queue.add(p.right);
                }
            }
            res.add(list);
        }

        return res;
    }

    public static void main(String[] args) {
        BiTree biTree=new BiTree();
        Integer[] nodes=new Integer[]{
                1,2,3,null,null,null,null
        };
        biTree.setTree(nodes);
        System.out.println(biTree.root.toString());
        biTree.preOrder(biTree.root);
    }
}

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

基本

/**
 * 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;
 *     }
 * }
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

94. 二叉树的中序遍历

递归中序


class Solution {
   
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        inorder(root,list);
        return list;
    }
    public void inorder(TreeNode root,List<Integer> list){
         if(root!=null){
            inorder(root.left,list);
            list.add(root.val);
            inorder(root.right,list);
        }
        
    }


}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

非递归中序1


class Solution {
   
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){//当前结点指针及栈均空,则结束
            while(cur!=null){//访问根结点,根指针进栈,进入左子树
                stack.push(cur);
                cur=cur.left;
            }
            if(!stack.isEmpty()){
                cur=stack.pop();
                list.add(cur.val);
                cur=cur.right;//根指针退栈,进入其右子树
            }
        }

        return list;
    }
   


}


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

非递归中序2




class Solution {
   
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){//当前结点指针及栈均空,则结束
            if(cur!=null){//访问根结点,根指针进栈,进入左子树
                stack.push(cur);
                cur=cur.left;
            }
            else{
                cur=stack.pop();
                list.add(cur.val);
                cur=cur.right;//根指针退栈,进入其右子树
            }
        }

        return list;
    }
   


}


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

100. 相同的树


class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
         if(p==null&&q==null) return true;
         if(p==null||q==null) return false;
         return p.val==q.val&&isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}
1
2
3
4
5
6
7
8

101. 对称二叉树

我先做的101，后做的100
可以像100简化代码


class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        TreeNode leftTree=root.left;
        TreeNode rightTree=root.right;
        return like(leftTree,rightTree);
    }
    public boolean like(TreeNode t1,TreeNode t2){
        boolean like1,like2;
        if(t1==null&&t2==null) return true;
        if(t1==null||t2==null) return false;
       
        if(t1.val==t2.val) {
            TreeNode l1=t1.left;
            TreeNode r1=t1.right;
            TreeNode l2=t2.left;
            TreeNode r2=t2.right;
            like1=like(l1,r2);
            like2=like(l2,r1);
            return like1&&like2;
        }
        return false;
      
      
    }
}
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

104. 二叉树的最大深度

简单
1.4K
相关企业
给定一个二叉树，找出其最大深度。

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

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

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

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。
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() {}
 *     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 1 + Math.max(maxDepth(root.left),maxDepth(root.right)) ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

108. 将有序数组转换为二叉搜索树

简单
1.2K
相关企业
给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。

高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：


输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
1
2
3
4
5
6

示例 2：


输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
1
2
3
4
5
6

中位数作为根节点，由顶至底
每次都是如此
递归

/**
 * 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 TreeNode sortedArrayToBST(int[] nums) {
        if(nums==null||nums.length==0){
            return null;
        }
        return create(nums,0,nums.length-1);
    }

    public TreeNode create(int[] nums,int left,int right){
        if(left>right){
            return null;
        }

        int mid=(left+right)/2;
        TreeNode root=new TreeNode(nums[mid]);
        root.left=create(nums,left,mid-1);
        root.right=create(nums,mid+1,right);
        return root;
    }
}
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

110. 平衡二叉树

简单
1.2K
相关企业
给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。

示例 1：


输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：


输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：

输入：root = []
输出：true
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

提示：

树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104

/**
 * 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 boolean isBalanced(TreeNode root) {
         if (root==null){
            return true;
        }

        if (Math.abs(maxDepth(root.left) - maxDepth(root.right)) > 1) {
            return false;
        }

        return isBalanced(root.left)&&isBalanced(root.right);
    }

    public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return 1 + Math.max(maxDepth(root.left),maxDepth(root.right)) ;
    }
}
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

111. 二叉树的最小深度

深度优先搜索

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

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

class Solution {
   
    public int minDepth(TreeNode root) {
        if(root== null) return 0;
        
        if(root.left==null&&root.right==null){
            return 1;
        }
           
        int depth= Integer.MAX_VALUE;
        if(root.left!=null){
            depth=Math.min(depth,minDepth(root.left));
        }   
        if(root.right!=null){
            depth=Math.min(depth,minDepth(root.right));
        }
        return depth+1;


    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

144. 二叉树的前序遍历

递归先序


class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        preorder(root,list);
        return list;
    }
    public void preorder(TreeNode root,List<Integer> list){
        if(root!=null){
            list.add(root.val);
            preorder(root.left,list);
            preorder(root.right,list);

        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

非递归先序


class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){//当前结点指针及栈均空,则结束
            while(cur!=null){//访问根结点,根指针进栈,进入左子树
                list.add(cur.val);
                stack.push(cur);
                cur=cur.left;
            }
            if(!stack.isEmpty()){
                cur=stack.pop();//根指针退栈,进入其右子树
                cur=cur.right;
            }
        }
        return list;
    }
   

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

145. 二叉树的后序遍历

递归后序

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        postorder(root,list);
        return list;
    }
    public void postorder(TreeNode root,List<Integer> list){
        if(root!=null){
            postorder(root.left,list);
            postorder(root.right,list);
            list.add(root.val);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

非递归后序

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root,next=null;
        while(cur!=null||!stack.isEmpty()){//当前结点指针及栈均空,则结束
            while(cur!=null){//访问根结点,根指针进栈,进入左子树
                stack.push(cur);
                 cur=cur.left;
            }
            if(!stack.isEmpty()){
                cur=stack.peek();
                if(cur.right==null||cur.right==next){
                     //判断栈顶结点的有子树是否为空，右子树是否刚访问过
                     cur=stack.pop();
                    list.add(cur.val);
                    next=cur;
                    cur=null;
                }else{
                    cur=cur.right;
                }
               
            }
        }


        return list;
    }
  
}
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

Offer

剑指 Offer 27. 二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9
1
2
3
4
5

镜像输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1
1
2
3
4
5

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

剑指 Offer 28. 对称的二叉树 101

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

package data.tree.offer;

import data.tree.BiTree;
import data.tree.TreeNode;

/**
 * @author CSDN@日星月云
 * @date 2022/11/1 18:13
 * 剑指 Offer 28. 对称的二叉树
 */
public class IsSymmetric {
    public static void main(String[] args) {
        BiTree biTree=new BiTree();
        Integer[] datas={1,2,2,3,4,4,3};
        biTree.setTree(datas);
        System.out.println(biTree.levelOrder(biTree.root));
        System.out.println("=====================");

        System.out.println(isSymmetric(biTree.root));

    }

    public static boolean isSymmetric(TreeNode root) {
        if (root==null){
            return true;
        }
        return like(root.left,root.right);

    }

    public static boolean like(TreeNode t1,TreeNode t2){
        if (t1==null&&t2==null){
            return true;
        }
        if(t1==null||t2==null){
            return false;
        }

        return t1.val==t2.val
            && like(t1.left,t2.right)
            && like(t1.right,t2.left);
    }

}

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

剑指 Offer 32 - II. 从上到下打印二叉树 II 102

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

/**
 * 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>> lists=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList();
        if(root==null){
            return lists;
        }

        queue.add(root);
        while (!queue.isEmpty()){
            List<Integer> list=new ArrayList<>();
            int count= queue.size();
            for (int i = 0; i <count; i++) {
                TreeNode p=queue.remove();
                list.add(p.val);
                if (p.left!=null){
                    queue.add(p.left);
                }
                if (p.right!=null){
                    queue.add(p.right);
                }
            }
            lists.add(list);

        }
         return lists;
    }
    
   
}
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

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

给定一棵二叉搜索树，请找出其中第 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

中序遍历(左根右)，就是按从小到大排序
中序遍历(右根左)，就是按从大到小排序，提前返回

class Solution {
   int res, k;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
    void dfs(TreeNode root) {
        if(root == null) return;
        dfs(root.right);
        if(k == 0) return;
        if(--k == 0) res = root.val;
        dfs(root.left);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

剑指 Offer 55 - I. 二叉树的深度 104

简单
216
相关企业
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：

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

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。
1
2
3
4
5
6
7
8
9
10

提示：

节点总数 <= 10000
注意：本题与主站 104 题相同：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int hl=maxDepth(root.left);
        int hr=maxDepth(root.right);
        return (hl>hr?hl:hr)+1;
    }
    


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

剑指 Offer 55 - II. 平衡二叉树

简单
319
相关企业
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过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 。

 
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

限制：

0 <= 树的结点个数 <= 10000
注意：本题与主站 110 题相同：https://leetcode-cn.com/problems/balanced-binary-tree/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        if(Math.abs(depth(root.left)-depth(root.right))>1){
            return false;
        }
        return isBalanced(root.left)&&isBalanced(root.right);

    }
    public int depth(TreeNode root){
        if(root==null){
            return 0;
        }
        int hl=depth(root.left);
        int hr=depth(root.right);
        return (hl>hr?hl:hr)+1;
    }
    
}
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

剑指 Offer II 052. 展平二叉搜索树

简单
45
相关企业
给你一棵二叉搜索树，请按中序遍历将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

示例 1：

输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
示例 2：

输入：root = [5,1,7]
输出：[1,null,5,null,7]

提示：

树中节点数的取值范围是 [1, 100]
0 <= Node.val <= 1000

注意：本题与主站 897 题相同： https://leetcode-cn.com/problems/increasing-order-search-tree/

class Solution {
    public TreeNode increasingBST(TreeNode root) {
        TreeNode newRoot=new TreeNode(-1);
        List<Integer> list=new ArrayList<>();
        inOrder(root,list);
        TreeNode cur=newRoot;
        for(Integer i:list){
            cur.right=new TreeNode(i);
            cur=cur.right;
        }
        return newRoot.right;
      
    }

    public void inOrder(TreeNode root,List list){
        if(root!=null){
            inOrder(root.left,list);
            list.add(root.val);
            inOrder(root.right,list);
        }
    }

   
}

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

最后不好处理，所以需要第一个不是有效数据-1

[[1], [2], [3], [4], [5], [6], [7], [8], [9], [0]]
1

面试题 04.02. 最小高度树 108

相同 108. 将有序数组转换为二叉搜索树

简单
140
相关企业
给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。

示例:
给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

          0 
         / \ 
       -3   9 
       /   / 
     -10  5 
1
2
3
4
5
6
7
8
9
10

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return create(nums,0,nums.length-1);
    }
    public TreeNode create(int[] nums,int left,int right){
        if(left>right){
            return null;
        }
        int mid=(left+right)/2;
        TreeNode root=new TreeNode(nums[mid]);
        root.left=create(nums,left,mid-1);
        root.right=create(nums,mid+1,right);
        return root;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

面试题 04.04. 检查平衡性 110

相同 110. 平衡二叉树

简单
94
相关企业
实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 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 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        if(Math.abs(depth(root.left)-depth(root.right))>1){
            return false;
        }
        return isBalanced(root.left)&&isBalanced(root.right);
    }
    public int depth(TreeNode root){
        if(root==null){
            return 0;
        }
        return Math.max(depth(root.left),depth(root.right))+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

面试题 17.12. BiNode II052

和剑指 Offer II 052. 展平二叉搜索树

简单
126
相关企业
二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。

返回转换后的单向链表的头节点。

注意：本题相对原题稍作改动

示例：

输入： [4,2,5,1,3,null,6,0]
输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]
提示：
1
2
3
4
5

节点数量不会超过 100000。

相关标签
《程序员面试金典（第 6 版）》独家授权

class Solution {
    public TreeNode convertBiNode(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        inOrder(root,list);
        TreeNode newRoot=new TreeNode(-1);
        TreeNode cur=newRoot;
        for(Integer i:list){
            cur.right=new TreeNode(i);
            cur=cur.right;
        }
        return newRoot.right;
    }

    public void inOrder(TreeNode root,List list){
        if(root!=null){
            inOrder(root.left,list);
            list.add(root.val);
            inOrder(root.right,list);
        }
       
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

相关阅读:
景区AR虚拟三维场景沉浸式体验成为新兴的营销手段
 springboot基于Java的电影院售票与管理系统毕业设计源码011449
C++ - 智能指针 - auto_ptr - unique_ptr - std::shared_ptr - weak_ptr
后台管理---删除功能
 一年前端面试打怪升级之路
 宝塔控制面板登陆不进去_宝塔磁盘已满
 Spark大数据处理使用Scala集成开发环境
 SpringBoot 自定义注解异步记录复杂日志
 图床项目进度（三）——文件展示页
 Linux驱动开发——（五）内核中断
原文地址：https://blog.csdn.net/qq_51625007/article/details/127559506

树【LeetCode】

树【LeetCode】

前言

树 简单

创建树

TreeNode

BiTree

基本

94. 二叉树的中序遍历

100. 相同的树

101. 对称二叉树

104. 二叉树的最大深度

108. 将有序数组转换为二叉搜索树

110. 平衡二叉树

111. 二叉树的最小深度

144. 二叉树的前序遍历

145. 二叉树的后序遍历

Offer

剑指 Offer 27. 二叉树的镜像

剑指 Offer 28. 对称的二叉树 101

剑指 Offer 32 - II. 从上到下打印二叉树 II 102

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

剑指 Offer 55 - I. 二叉树的深度 104

剑指 Offer 55 - II. 平衡二叉树

剑指 Offer II 052. 展平二叉搜索树

面试题 04.02. 最小高度树 108

面试题 04.04. 检查平衡性 110

面试题 17.12. BiNode II052

树简单