2020-3-14

300.最长上升子序列

✒解题思路：

1. DP $$if(num[i]>num[j]) dp[i] = max(dp[i],dp[j]+1)$$

   class Solution {
   	public int lengthOfLIS(int[] nums) {
   		int len = nums.length;
   		if (len < 2) {
   			return len;
   		}
   		int[] dp = new int[len];
   		Arrays.fill(dp, 1);//初始化为1
   		int maxLenghth = 1;
   		for (int i = 1; i < len; i++) {
   			for (int j = 0; j < i; j++) {
   				if (nums[i] > nums[j]) {
   					dp[i] = Math.max(dp[j] + 1, dp[i]);
   				}
   			}
   			maxLenghth = Math.max(dp[i], maxLenghth);
   		}
   		return maxLenghth;
   	}
   }

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

✒解题思路：

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 sortedArrayToBST(int[] nums) {
		return helper(nums, 0, nums.length - 1);
	}
	public TreeNode helper(int[] nums, int start, int end) {
		if (start > end) {
			return null;
		}
		int mid = start + (end - start) / 2;//防止溢出
		TreeNode root = new TreeNode(nums[mid]);
		root.left = helper(nums, start, mid - 1);
		root.right = helper(nums, mid + 1, end);
		return root;
	}
}

110.平衡二叉树

✒解题思路：

1. 递归遍历每个节点，获取左右节点的深度，比较深度之差。

/**
 * 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;
		}
		return Math.abs(getHight(root.left) - getHight(root.right)) < 2 && isBalanced(root.left) && isBalanced(root.right);
	}
	private int getHight(TreeNode root) {
		if (root == null) {
			return -1;
		}
		return 1 + Math.max(getHight(root.left), getHight(root.right));
	}
}

112.路径总和

✒解题思路：

1. 递归遍历根节点，当该节点不是叶子节点时，分别向左右递归，当左右节点为空时判断sum是否为零。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public boolean hasPathSum(TreeNode root, int sum) {
		if (root == null) {
			return false;
		}
		sum -= root.val;
		if (root.left == null && root.right == null) {
			return sum == 0;
		}
		return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
	}
}

257.二叉树的所有路径

✒解题思路：

1. 官方：最直观的方法是使用递归。在递归遍历二叉树时，需要考虑当前的节点和它的孩子节点。如果当前的节点不是叶子节点，则在当前的路径末尾添加该节点，并递归遍历该节点的每一个孩子节点。如果当前的节点是叶子节点，则在当前的路径末尾添加该节点后，就得到了一条从根节点到叶子节点的路径，可以把该路径加入到答案中。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public List<String> binaryTreePaths(TreeNode root) {
		LinkedList<String> paths = new LinkedList<>();
		constructPath(root, "", paths);
		return paths;
	}

	private void constructPath(TreeNode root, String path, LinkedList<String> paths) {
		if (root == null) {
			return;
		}
		path += Integer.toString(root.val);
		if (root.left == null && root.right == null) {
			paths.add(path);
		} else {
			path += "->";//当前节点不是叶子节点，继续遍历
			constructPath(root.left, path, paths);
			constructPath(root.right, path, paths);
		}
	}
}

559.N叉树的最大深度

✒解题思路：

1. 遍历各子节点即可，与二叉树思路相同

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
	public int maxDepth(Node root) {
		if (root == null) {
			return 0;
		}
		int max = 0;
		for (Node node : root.children) {
			max = Math.max(max, maxDepth(node));
		}
		return max + 1;
	}
}

872.叶子相似的树

✒解题思路：

1. 用list将树的叶子节点保存起来，再进行比较

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public boolean leafSimilar(TreeNode root1, TreeNode root2) {

		ArrayList<Integer> nums1 = new ArrayList<>();
		ArrayList<Integer> nums2 = new ArrayList<>();
		getNums(root1, nums1);
		getNums(root2, nums2);
		return nums1.equals(nums2);
	}

	private void getNums(TreeNode root, ArrayList<Integer> nums) {
		if (root == null) {
			return;
		}
		if (root.left == null && root.right == null) {
			nums.add(root.val);
		}
		getNums(root.left, nums);
		getNums(root.right, nums);
	}
}