24khandsome's Blog

24khandsome's Blog

leetcode100-树

发表于 更新于 分类于
leetcode热题100

二叉树

94. 二叉树的中序遍历

image-20240120175425011

二叉树的先序、中序、后序遍历是指遍历一颗二树时遍历到父节点的顺序的先后

1、先序：父左右

2、中序：左父右

3、后序：左右父

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class A1_94{
    List<Integer> result = new ArrayList<>();
    public List<Integer> inorderTraversal1(TreeNode root) {
        inOrderDfs(root);
        return result;
    }
    private void inOrderDfs(TreeNode root) {
        if(root == null){
            return;
        }
        inOrderDfs(root.left);
        result.add(root.val);
        inOrderDfs(root.right);
    }
}

104. 二叉树的最大深度

image-20240120180330854

1
2
3
4
5
6
7
8
9
public class A2_104{
    public int maxDepth(TreeNode root) {
        if(null == root){
            return 0;
        }else{
            return 1 + Math.max(maxDepth(root.left) ,maxDepth(root.right) );
        }
    }
}

226. 翻转二叉树

image-20240120180820029

1
2
3
4
5
6
7
8
9
10
11
public TreeNode invertTree(TreeNode root) {
    if(root == null){
        return root;
    }
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);

    root.right = left;
    root.left = right;
    return root;
}

101. 对称二叉树

image-20240120181423723

思路：定义出递归函数

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
public class A4_101{
    /**
     * 递归
     * @param root
     */
    public boolean isSymmetric(TreeNode root) {
        if(null == root){
            return true;
        }
        return checkSymmetric(root.left,root.right);
    }

    public boolean checkSymmetric(TreeNode left,TreeNode right){
        if(null == left && null == right){
            return true;
        }
        if(null == left || null == right){
            return false;
        }
        return left.val == right.val && checkSymmetric(left.left,right.right) && checkSymmetric(left.right,right.left);
    }

    /**
     * 迭代写法
     * @param root
     */
    public boolean isSymmetric1(TreeNode root) {
        if(null == root){
            return true;
        }
        //这里不能用ArrayDeque,因为ArrayDeque无法存储null
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        queue.add(root);
        while(queue.size() > 0){
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            if(left == null && right == null){
                continue;
            }
            if((left == null || right == null) || left.val != right.val){
                return false;
            }

            queue.add(left.left);
            queue.add(right.right);
            if(left == right){
                //queue.add(root);做了2次，避免重复比较
                continue;
            }
            queue.add(left.right);
            queue.add(right.left);
        }
        return true;
    }
}

543. 二叉树的直径

image-20240121154853850

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
private Integer max = 0;
   public int diameterOfBinaryTree(TreeNode root) {
       maxDepth(root);
       return max;
   }

   /**
    * 首先我们知道一条路径的长度为该路径经过的节点数减一，
    * 所以求直径（即求路径长度的最大值）等效于求路径经过节点数的最大值减一。
    * root直径 = root.lDept + root.rDept + 1 - 1 = root.lDept + root.rDept
    * root深度 = 1 + Math.max(lDept, rDept)
    * f(x)：查找root的最大深度的过程中(查找以root为根的最大深度)
    * 1、左子树的f(x.left) + f(x.righy) =  x节点的直径
    * 2、深度遍历过程中,计算最大的 MAX{f(x.left) + f(x.righy)}
    * @param root
    * @return
    */
   public int maxDepth(TreeNode root) {
       if(null == root){
           return 0;
       }else{
           int lDept = maxDepth(root.left);
           int rDept = maxDepth(root.right);
           max = Math.max(max,lDept + rDept);
           return 1 + Math.max(lDept, rDept);
       }
   }

102. 二叉树的层序遍历

image-20240121155143461

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
public class A6_102{
    List<List<Integer>> result = new ArrayList<>();
    /**
     * 利用深度遍历，且传入层数
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder1(TreeNode root) {
        dfs(root,0);
        return result;
    }
    public void dfs(TreeNode node,int level){
        if(node == null){
            return;
        }
        if(result.size() == level){
            result.add(new ArrayList<>());
        }
        result.get(level).add(node.val);
        dfs(node.left,level+1);
        dfs(node.right,level+1);
    }
    /**
     * 利用队列实现宽度遍历
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()){
            int n = queue.size();
            List<Integer> data = new ArrayList<>();
            while(n > 0){
                TreeNode node = queue.poll();
                data.add(node.val);
                if(null != node.left){
                    queue.add(node.left);
                }
                if(null != node.right){
                    queue.add(node.right);
                }
                n--;
            }
            result.add(data);
        }
        return result;
    }
}

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

image-20240121161141492

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
public TreeNode sortedArrayToBST(int[] nums) {
    return sortedArrayToBST(nums,0,nums.length-1);
}
/**
 * 有序数组 = 二叉搜索树的中序遍历
 * 1、以nums的中点为根节点root，左右两边分别比root小和大，两边再递归这个过程得到leftResult,rightResult,
 * 2、root.left = leftResult,root.right = rightResult
 *
 * @param nums
 * @param begin
 * @param end
 * @return
 */
public TreeNode sortedArrayToBST(int[] nums,int begin,int end) {
    if (null == nums || nums.length == 0 || end - begin < 0){
        return null;
    }
    int mid = (begin + end) / 2;
    TreeNode root = new TreeNode(nums[mid]);
    //可以不做判断
    if(mid != begin){
        root.left = sortedArrayToBST(nums,begin,mid-1);
    }
    if(mid != end){
        root.right = sortedArrayToBST(nums,mid+1,end);
    }
    return root;
}

98. 验证二叉搜索树

image-20240121165201253

解法一：中序+前值preVal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private long pre = Long.MIN_VALUE;
/**
 * 也是利用中序遍历的原理，pre表示已经遍历的中序遍历的数组的最右值，参考方法二
 * @param node
 * @return
 */
public boolean isValidBST1(TreeNode node) {
    if(node == null){
        return true;
    }
    if(!isValidBST1(node.left) || pre >= node.val){
        return false;
    }
    pre = node.val;
    return isValidBST1(node.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
26
public boolean isValidBST2(TreeNode root) {
    if(root == null){
        return true;
    }
    List<Integer> inorderList = new ArrayList<>();
    inOrderRead(root,inorderList);
    for (int i = 0; i < inorderList.size() - 1; i++) {
        if(inorderList.get(i) >= inorderList.get(i+1)){
            return false;
        }
    }
    return true;
}

private void inOrderRead(TreeNode root,List<Integer> list) {
    if(root == null){
        return;
    }
    if(root.left != null){
        inOrderRead(root.left,list);
    }
    list.add(root.val);
    if(root.right != null){
        inOrderRead(root.right,list);
    }
}

解法三：先序遍历思维 + 左右边界判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 递归（先序遍历）
 * @param root
 * @return
 */
public boolean isValidBST(TreeNode root) {
    return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
}

public boolean isValidBST(TreeNode node,long lower,long upper) {
    if(node == null){
        return true;
    }
    if(node.val <= lower || node.val >= upper){
        return false;
    }
    return  isValidBST(node.left,lower,node.val)
            && isValidBST(node.right,node.val,upper);
}

230. 二叉搜索树中第K小的元素

image-20240121164533955

解法一：中序遍历 + count–

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
private int result = 0;
private int count = 0;

/**
 * 利用中序遍历
 * @param root
 * @param k
 * @return
 */
public int kthSmallest1(TreeNode root, int k) {
    count = k;
    dfs(root);
    return result;
}

public void dfs(TreeNode node){
    if(node == null){
        return;
    }
    dfs(node.left);
    count--;
    if(count == 0){
        result = node.val;
    }
    dfs(node.right);
}

解法二：中序遍历 + List维护所有访问路径，result = list.get（k-1）

解法三：小顶堆 + 遍历第k个

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
PriorityBlockingQueue<Integer> queue;
/**
 * 小顶推 + 任意一种遍历
 * @param root
 * @param k
 * @return
 */
public int kthSmallest2(TreeNode root, int k) {
    queue = new PriorityBlockingQueue(k);
    inOrder(root);
    while(!queue.isEmpty()){
        k--;
        Integer poll = queue.poll();
        if(k == 0){
            return poll;
        }
    }
    return 0;
}

private void inOrder(TreeNode root) {
    if(root == null){
        return;
    }
    queue.offer(root.val);
    inOrder(root.left);
    inOrder(root.right);
}

199. 二叉树的右视图

image-20240121175307847

方法一：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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class A10_199 {
    List<Integer> result = new ArrayList<>();
    public List<Integer> rightSideView1(TreeNode root) {
        dfs(root,0);
        return result;
    }

    public void dfs(TreeNode root,int level){
        if(root == null){
            return;
        }
        if(result.size() == level){
            result.add(root.val);
        }
        level = level + 1;
        dfs(root.right,level);
        dfs(root.left,level);
    }


    /**
     * 宽度优先便利
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        Queue<TreeNode> queue = new ArrayDeque();
        queue.add(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size > 0){
                TreeNode node = queue.poll();
                if(node.left != null){
                    queue.add(node.left);
                }
                if(node.right != null){
                    queue.add(node.right);
                }
                size--;
                if(size == 0){
                    result.add(node.val);
                }
            }
        }
        return result;
    }
}

114. 二叉树展开为链表

image-20240121215727024

方法一：深度遍历+自定义递归，在原空间上边展开、边遍历。

方法二：先序遍历+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
31
32
33
34
/**
 * 利用自生定义递归
 * 1、将左子树插入到右子树的地方
 * 2、将原来的右子树接到左子树的最右边节点
 * 考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null
 * f(x) = {
 *     left = x.left;
 *     right = x.right;
 *     x.left = null;
 *     x.right = f(left);
 *     x = x.right 递归到底;
 *     x.right = f(right)
 *     
 * }
 * @param root
 */
public void flatten(TreeNode root) {
    if(root == null){
        return;
    }
    TreeNode left = root.left;
    TreeNode right = root.right;

    flatten(left);
    //1、将左子树插入到右子树的地方
    root.right = left;
    root.left = null;
    //2、将原来的右子树接到左子树的最右边节点
    while(root.right != null){
        root = root.right;
    }
    flatten(right);
    root.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
/**
 * 借助List<TreeNode>记录先序便利节点
 * @param root
 */
public void flatten1(TreeNode root) {
    dfs(root);
    TreeNode dummyHead = new TreeNode();
    TreeNode cur = dummyHead;
    for (int i = 0; i < nodes.size(); i++) {
        TreeNode treeNode = nodes.get(i);
        cur.left = null;
        cur.right = treeNode;
        cur = cur.right;
    }
}

public void dfs(TreeNode root){
    if(root == null){
        return;
    }
    nodes.add(root);
    dfs(root.left);
    dfs(root.right);

}

105. 从前序与中序遍历序列构造二叉树

image-20240121222906387

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
public TreeNode buildTree(int[] preorder, int[] inorder) {
    int preLength = preorder.length;
    Map<Integer,Integer> inMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        int i1 = inorder[i];
        inMap.put(i1,i);
    }
    return buildTree(preorder,0,preLength-1,0,inorder.length-1,inMap);
}

/**
 * 1XXYYYY pre 根节点|左子树|右子树
 * XX1YYYY in  左子树|根节点|右子树
 */
private TreeNode buildTree(int[] preorder,int preLeft, int preRight,int inLeft, int inRight, Map<Integer, Integer> inMap) {
    if((preLeft > preRight) || (inLeft > inRight)){
        return null;
    }
    //先序的第一个数是父节点
    int root = preorder[preLeft];
    TreeNode rootNode = new TreeNode(root);
    Integer inRootIndex = inMap.get(root);
    //inRootIndex-inLeft:左子树长度
    rootNode.left = buildTree(preorder,preLeft+1,inRootIndex-inLeft+preLeft,inLeft,inRootIndex-1,inMap);
    rootNode.right = buildTree(preorder,inRootIndex-inLeft+preLeft+1,preRight,inRootIndex+1,inRight,inMap);
    return rootNode;
}

437. 路径总和 III

image-20240801154343785

解法一：递归 + 前缀和 + 回溯

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
private Integer result = 0;
/**
 * 递归 + 前缀和 + 回溯
 * path(x,y) = path(x)- path(y)：从根节点到x的path -  从根节点到y的path = path(x,y)
 * 假设 path(x,y) = target,则满足条件
 * 利用前缀和prefix<Integer path,Integer count> 来记录深度遍历过程中，从根节点到某个节点的和为path的个数
 * @param root
 * @param targetSum
 * @return
 */
public int pathSum(TreeNode root, int targetSum) {
    if(root == null){
        return 0;
    }
    Map<Long,Integer> prefixMap = new HashMap<>();
    //存在从root到node节点的sum = target的场景
    prefixMap.put(0L,1);
    dfs(root,targetSum,0L,prefixMap);
    return result;
}

private void dfs(TreeNode root,int targetSum,long curSum,Map<Long,Integer> prefix){
    if(root == null){
        return;
    }
    int val = root.val;
    curSum += val;
    result += prefix.getOrDefault(curSum-targetSum,0);
    //保存当前节点的前缀和结果
    prefix.put(curSum,prefix.getOrDefault(curSum,0) + 1);
    //向下递归
    dfs(root.left,targetSum,curSum,prefix);
    dfs(root.right,targetSum,curSum,prefix);
    //回溯
    prefix.put(curSum,prefix.getOrDefault(curSum,0) - 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
31
/**
 * 深度便利+递归
 * pathSum(root,target):root下存在路径值为target的路径个数，不要求从root开始
 * @param root
 * @param targetSum
 * @return
 */
public int pathSum1(TreeNode root, int targetSum) {
    if(root == null){
        return 0;
    }
    return pathFirtstSum(root, (long) targetSum) + pathSum1(root.left,targetSum) + pathSum1(root.right,targetSum);
}

/**
 * pathFirtstSum(root,target):以root为路径第一个节点到某个节点的路劲值为target的个数
 * @param rooTreeNode
 * @param target
 * @return
 */
public int pathFirtstSum(TreeNode rooTreeNode, Long target){
    int result = 0;
    if(rooTreeNode == null){
        return 0;
    }
    int val = rooTreeNode.val;
    if(val ==  target){
        result++;
    }
    return result + pathFirtstSum(rooTreeNode.left,target-val) + pathFirtstSum(rooTreeNode.right,target-val);
}

236. 二叉树的最近公共祖先

image-20240122224457197

解法一：利用递归+List找出p、q的路径，比对路径

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
/**
 * 深度遍历+找出p，q2条节点路径，比对路径
 * @param root
 * @param p
 * @param q
 * @return
 */
public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
    List<TreeNode> pList = new ArrayList<>();
    List<TreeNode> qList = new ArrayList<>();
    dfs2(root,p,pList);
    dfs2(root,q,qList);
    for (int i = 0; i < pList.size() ; i++) {
        if(qList.contains(pList.get(i))){
            return pList.get(i);
        }
    }

    return ans;
}

/**
 * 能从root往下找到p和q
 * @param root
 * @param target
 * @return
 */
private boolean dfs2(TreeNode root,TreeNode target,List<TreeNode> list){
    if(root == null){
        return false;
    }
    if(root == target){
        list.add(root);
        return true;
    }
    if(dfs2(root.left,target,list)){
        list.add(root);
        return true;
    }
    if(dfs2(root.right,target,list)){
        list.add(root);
        return true;
    }
    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
private TreeNode ans;
	/**
     * 递归深度遍历
     * @param root
     * @param p
     * @param q
     * @return
     */
public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
    dfs1(root,p,q);
    return ans;
}

public boolean dfs1(TreeNode root,TreeNode p,TreeNode q){
    if(root == null){
        return false;
    }
    boolean left = dfs1(root.left, p, q);
    boolean right = dfs1(root.right, p, q);
    boolean rootIsOneOfTarget = root.val == p.val || root.val == q.val;
    if((left && right) || ((left || right) && rootIsOneOfTarget)){
        //1、root的左右子树分别包含p或q
        //2、root的左右子树包含p或q 且 root = p或q
        ans = root;
    }
    //向上传
    return left || right || rootIsOneOfTarget;
}

124. 二叉树中的最大路径和

image-20240122232612668

解法一：递归+以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
private Integer max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
    dfsMaxPath(root);
    return max;
}

/**
 * f(x)以root节点为开始节点的一条路径的最大值
 * 1、root.val 本身
 * 2、root.val + f(root.left)
 * 3、root.val + f(root.right)
 * 4、取最大值
 * 在递归f(x)的过程中，计算
 * 经过root的最大路路径=Max(val+ f(root.left),val+f(root.right),val+ f(root.left)+ f(root.right))
 * @param root
 * @return
 */
public int dfsMaxPath(TreeNode root) {
    if(null == root){
        return 0;
    }

    int lDept = Math.max(dfsMaxPath(root.left),0);
    int rDept = Math.max(dfsMaxPath(root.right),0);
    int val = root.val;
    this.max = Math.max(val + lDept + rDept,this.max);
    return Math.max(lDept,rDept) + val;
}