LeetCode 2020年7月15日

一、leetcode-543

1、题目大意

给定一颗二叉树，求出树中最长的那条路径长度。

例如：对于下列这颗树，最长路径为3，[4,2,1,3]或[5,2,1,3]，路径长度是边的个数。

1
2
3
4
5
    1
   / \
  2   3
 / \     
4   5

2、思路

对每颗子树求得最长路径取最大值。

对于指定某个根的树来说，求经过该根节点的最长路径就是分别求该根结点到左右子树叶子结点的最长路径。

3、代码

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
/**
 * 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 {
    int Max; //取所有子树的最长路径
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null)return 0;
        Max = 0;
        solve(root);
        return Max;
    }
    int solve(TreeNode root) {
        if (root == null)return 0;
        int a = solve(root.left);
        int b = solve(root.right);
        Max = Math.max(Max, a + b); //更新最大值
        return Math.max(a, b) + 1; //返回左右子树中长的那一条路径的长度
    }
}

二、leetcode-1325

1、题目大意

给定一颗二叉树和一个target，删除该二叉树中叶子节点值为target的所有结点。

如：root = [1,2,3,2,null,2,4], target = 2

img

则最后树为[1,null,3,null,4]。

2、思路

遍历二叉树，需采用后序遍历，对叶子结点进行判断，判断叶子结点值是否为target，若是更改它的父节点对应的左右结点为null。

3、代码

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
/**
 * 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 removeLeafNodes(TreeNode root, int target) {
        //设置一个父结点，将树根结点作为其左结点或右结点，因为可能存在所有结点均被删除
        TreeNode parent = new TreeNode(-1);
        parent.left = root; 
        solve(parent, root, target);
        return parent.left;
    }

    public void solve(TreeNode parent, TreeNode root, int target) {
        if (root == null) return;
        solve(root, root.left, target);
        solve(root, root.right, target);
        //如果该结点为叶子结点且值为target，则找到它对应是parent的左儿子还是右儿子
         if (root.val == target && root.left == null && root.right == null) {
            if (parent.left == root)parent.left = null;
            else parent.right = null;
        }
    }
}

最后更新： 2020年07月15日 20:45

原始链接： http://tanruidd.github.io/2020/07/15/leetcode-2020-7-15/