Valid Parentheses

发表于 2016-04-09

算法分类：Stack

url：https://leetcode.com/problems/valid-parentheses/

题目

20. Valid Parentheses
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true
Example 2:

Input: "()[]{}"
Output: true
Example 3:

Input: "(]"
Output: false

Java解法

class Solution {
    public boolean isValid(String s) {
        Stack<String> stack = new Stack<>();
        char[] chArr = s.toCharArray();
        for (char ch : chArr) {
            String top = stack.isEmpty() ? null : stack.peek();
            String c = String.valueOf(ch);
            if (null == top) {
                stack.push(c);
            } else if (top.equals("{")) {
                if (c.equals("}")) {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            } else if (top.equals("[")) {
                if (c.equals("]")) {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            } else if (top.equals("(")) {
                if (c.equals(")")) {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            } else {
                stack.push(c);
            }
        }
        if (stack.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }
}

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        HashMap<Character, Character> map = new HashMap<Character, Character>() {{
            put('}', '{');
            put(']', '[');
            put(')', '(');
        }};
        char[] chArr = s.toCharArray();
        for (char ch : chArr) {
            Character top = stack.isEmpty() ? null : stack.peek();
            if (null == top) {
                stack.push(ch);
            } else if (top == map.get(ch)) {
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

Python解法

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        map = {u'}':u'{', u']':u'[', u')':u'('}
        for ch in s:
            top = u'#' if (len(stack) == 0) else stack[-1]
            if map.has_key(ch) and top == map[ch]:
                stack.pop()
            else:
                stack.append(ch)

        return 0 == len(stack)

Unique Binary Search Trees ii

发表于 2016-04-07

算法：二叉搜索树

url：https://leetcode-cn.com/problems/unique-binary-search-trees-ii/

题目

给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
示例:

输入: 3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

分析

首先来计数需要构建的二叉树数量。可能的二叉搜素数数量是一个卡特兰数。

我们跟随上文的逻辑，只是这次是构建具体的树，而不是计数。

算法

我们从序列 1 ..n 中取出数字 i，作为当前树的树根。于是，剩余 i - 1 个元素可用于左子树，n - i 个元素用于右子树。
如前文所述，这样会产生 G(i - 1) 种左子树和 G(n - i) 种右子树，其中 G 是卡特兰数。

现在，我们对序列 1 … i - 1 重复上述过程，以构建所有的左子树；然后对 i + 1 … n 重复，以构建所有的右子树。

这样，我们就有了树根 i 和可能的左子树、右子树的列表。

最后一步，对两个列表循环，将左子树和右子树连接在根上。

Java解法

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n <= 0) {
            return new LinkedList<TreeNode>();
        }
        return listTrees(1, n);        
    }
    
    public LinkedList<TreeNode> listTrees(int start, int end) {
        LinkedList<TreeNode> rootList = new LinkedList<TreeNode>();
        if(start > end) {
            rootList.add(null);
            return rootList;
        }
        for(int i=start; i<=end; ++i) {
            LinkedList<TreeNode> leftList = listTrees(start, i-1); 
            LinkedList<TreeNode> rightList = listTrees(i+1, end);
            for(TreeNode left : leftList) {
                for(TreeNode right : rightList) {
                    TreeNode cur = new TreeNode(i);
                    cur.left = left;
                    cur.right = right;
                    rootList.add(cur);
                }
            }
        }
        return rootList;
    }

}

Python解法

Two Ssum

发表于 2016-04-05

url：

https://leetcode.com/problems/two-sum/submissions/

题目：

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Java 解法：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

Python解法：

# https://leetcode.com/problems/two-sum/submissions/
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            x = target-nums[i];
            c = nums[0:i].count(x);
            if c > 0 and nums.index(x) != i:
                return [nums.index(x), i]

Recover Binary Search Tree

发表于 2016-04-03

算法：二叉搜索树，深度优先搜索

url：https://leetcode.com/problems/recover-binary-search-tree/

题目

99. Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.

Example 1:
Input: [1,3,null,null,2]
   1
  /
 3
  \
   2

Output: [3,1,null,null,2]
   3
  /
 1
  \
   2
Example 2:
Input: [3,1,4,null,null,2]
  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]
  2
 / \
1   4
   /
  3
Follow up:
A solution using O(n) space is pretty straight forward.
Could you devise a constant space solution?

分析

要求，不改变现有树结构的前提，使数恢复为二叉搜索树；
使用DFS便利二叉树，凡是不符合规则的节点都标记出来；
中序遍历，遍历结果有序，无序的节点就是不合格的节点

Java解法

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    TreeNode pre;
    TreeNode first, second;
    public void recoverTree(TreeNode root) {
        pre = new TreeNode(Integer.MIN_VALUE);
        inorder(root);
        swap(first, second);
    }
    public void inorder(TreeNode root) {
        if(null == root) return;
        inorder(root.left);
        if(pre.val >= root.val && pre.val != Integer.MIN_VALUE) {
            if(null == first) first = pre;
            second = root;
        }
        pre = root;
        inorder(root.right);
    }
    public void swap(TreeNode node1, TreeNode node2) {
        int tmp = node1.val;
        node1.val = node2.val;
        node2.val = tmp;
    }
}

public class MainClass {
    public static TreeNode stringToTreeNode(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if (input.length() == 0) {
            return null;
        }
    
        String[] parts = input.split(",");
        String item = parts[0];
        TreeNode root = new TreeNode(Integer.parseInt(item));
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);
    
        int index = 1;
        while(!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.remove();
    
            if (index == parts.length) {
                break;
            }
    
            item = parts[index++];
            item = item.trim();
            if (!item.equals("null")) {
                int leftNumber = Integer.parseInt(item);
                node.left = new TreeNode(leftNumber);
                nodeQueue.add(node.left);
            }
    
            if (index == parts.length) {
                break;
            }
    
            item = parts[index++];
            item = item.trim();
            if (!item.equals("null")) {
                int rightNumber = Integer.parseInt(item);
                node.right = new TreeNode(rightNumber);
                nodeQueue.add(node.right);
            }
        }
        return root;
    }
    
    public static String treeNodeToString(TreeNode root) {
        if (root == null) {
            return "[]";
        }
    
        String output = "";
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);
        while(!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.remove();
    
            if (node == null) {
              output += "null, ";
              continue;
            }
    
            output += String.valueOf(node.val) + ", ";
            nodeQueue.add(node.left);
            nodeQueue.add(node.right);
        }
        return "[" + output.substring(0, output.length() - 2) + "]";
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null) {
            TreeNode root = stringToTreeNode(line);
            
            new Solution().recoverTree(root);
            String out = treeNodeToString(root);
            
            System.out.print(out);
        }
    }
}

Python解法

单链表反转 —— 变形

发表于 2016-04-03

算法：单链表反转

题目

这其实是一道变形的链表反转题，大致描述如下

给定一个单链表的头节点 head,实现一个调整单链表的函数，使得每K个节点之间为一组进行逆序，并且从链表的尾部开始组起，头部剩余节点数量不够一组的不需要逆序。（不能使用队列或者栈作为辅助）

例如：
链表:1->2->3->4->5->6->7->8->null, K = 3。那么 6->7->8，3->4->5，1->2各位一组。调整后：1->2->5->4->3->8->7->6->null。其中 1，2不调整，因为不够一组。

解析

这道题的难点在于，是从链表的尾部开始组起的，而不是从链表的头部，如果是头部的话，那我们还是比较容易做的，因为你可以遍历链表，每遍历 k 个就拆分为一组来逆序。但是从尾部的话就不一样了，因为是单链表，不能往后遍历组起；

思路1：整体反转，然后从头开始截取 K个节点，被后续截图的K个节点的尾部连接；最后长度不足K的节点再局部反转作为队头

思路2：整体反转，

Java解法

class Node {
    int val;
    Node next;
    public Node(int d) { this.val = d; }
}
class Solution {
    public Node reverse(Node node) {
        Node pre = node;
        Node cur = node.next;
        node.next = null;
        Node tmp;
        while(cur!=null) {
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
    public Node reverseByK(Node node, int k) {
        Node tmp = node;
        for (int i=1; i<k && tmp != null; i++) {
            tmp = tmp.next;
        }
        if (tmp == null) {
            return node;
        }
        Node childList = tmp.next;
        tmp.next = null;
        Node retNode = reverse(node);
        Node newChildNode = reverseByK(childList, k);
        node.next = newChildNode;
        
        return retNode;
    }
    public static void main(String[] args) {
        Node link = null;
        Node tmp = link;
        for(int i=1; i<9; ++i) {
            if(null == tmp) {
            	tmp = new Node(i);
            	link = tmp;
            } else {
            	tmp.next = new Node(i);
            	tmp = tmp.next;
            }
        }
        Solution solution = new Solution();
        link = solution.reverse(solution.reverseByK(solution.reverse(link), 3));
        while(link!=null) {
            System.out.print(link.val + " ");
            link = link.next;
        }
    }
}

Python解法

Longest Palindromic Substring

发表于 2016-04-01

算法：动态规划

题目

URL：https://leetcode-cn.com/problems/longest-palindromic-substring/

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

分析

Java解法

扩展中心算法

import java.util.Stack;

public class Solution {
    public String longestPalindrome(String s) {
        String longestS=null, curS=null;
        for(int i=0; i<s.length(); ++i) {
            curS = palindrome(s.toCharArray(), i);
            if (null == curS) continue;
            if (null == longestS) longestS = curS;
            else {
                if (longestS.length() <= curS.length()) longestS = curS;
            }
        }
        return (null == longestS) ? "" : longestS;
    }
    public String palindrome(char[] chArr, int index) {
        Stack<Character> stack1 = new Stack<Character>();
        Stack<Character> stack2 = new Stack<Character>();
        int len1=0, len2=0;
        if(index-1>=0 && chArr[index] == chArr[index-1]) {
            for(int i=index-1; i>=0; --i) {
                int delta = index-1-i;
                if(index+delta>=chArr.length) break;
                if(chArr[i] == chArr[index+delta]) {
                    stack1.push(chArr[i]);
                } else {
                    break;
                }
            }
            len1 = stack1.size()*2;
        }
        if(index-2>=0 && chArr[index] == chArr[index-2]) {
            stack2.push(chArr[index-1]);
            for(int i=index-2; i>=0; --i) {
                int delta = index-2-i;
                if(index+delta>=chArr.length) break;
                if(chArr[i] == chArr[index+delta]) {
                    stack2.push(chArr[i]);
                } else {
                    break;
                }
            }
            len2 = stack2.size()*2 - 1;
        }
        // System.out.printf("%d, %d %c \n", len1, len2, chArr[index]);
        if (0==len1 && 0==len2) return String.valueOf(chArr[index]);
        if (len1>len2) {
            char[] res = new char[len1];
            for(int i=0; !stack1.isEmpty(); ++i) {
                char c = stack1.pop().charValue();
                res[i] = res[len1-1-i] = c;
            }
            return String.copyValueOf(res);
        } else {
            char[] res = new char[len2];
            for(int i=0; !stack2.isEmpty(); ++i) {
                char c = stack2.pop().charValue();
                res[i] = res[len2-1-i] = c;
            }
            return String.copyValueOf(res);
        }
    }
    public static void main(String[] args) {
            String s = "ba";
            String ret = new Solution().longestPalindrome(s);
            String out = (ret);
            System.out.print(out);
    }
}

同样解法的代码优化

class Solution {
	public String longestPalindrome(String s) {
		if (s == null || s.length() < 1)
			return "";
		int start = 0, end = 0;
		for (int i = 0; i < s.length(); i++) {
			int len1 = expandAroundCenter(s, i, i);
			int len2 = expandAroundCenter(s, i, i + 1);
			int len = Math.max(len1, len2);
			if (len > end - start) {
				start = i - (len - 1) / 2;
				end = i + len / 2;
			}
		}
		return s.substring(start, end + 1);
	}

	private int expandAroundCenter(String s, int left, int right) {
		int L = left, R = right;
		while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
			L--;
			R++;
		}
		return R - L - 1;
	}
}

动态规划的解法

public class App {
	public static void main(String[] args) {
		String s = "aba1ab";
		String ret = new Solution().longestPalindrome(s);
		String out = (ret);
		System.out.print(out);
	}
}
class Solution {
	public String longestPalindrome(String s) {
        if(null == s || s.length() <= 1) {
            return s;
        }
        String origin = s;
        String reverse = new StringBuffer(s).reverse().toString();
        int length = s.length();
        int[][] arr = new int[length][length];
        int maxLen = 0;
        int maxEnd = 0;
        for(int i=0; i<length; ++i) {
            for(int j=0; j<length; ++j) {
                if(origin.charAt(i) == reverse.charAt(j)) {
                    if(0==i || 0==j) {
                        arr[i][j] = 1;
                    } else {
                        arr[i][j] = arr[i-1][j-1] + 1;
                    }
                }
                if (arr[i][j]>= maxLen) {
                    int beforeRev = length-1 - j;
                    if(arr[i][j]-1+beforeRev == i) {
                        maxLen = arr[i][j];
                        maxEnd = i;
                    }
                }
            }
        }
        return s.substring(maxEnd-(maxLen-1), maxEnd+1);
    }
}

Python解法

Kth Largest Element in an Array

发表于 2016-03-29

算法：Heap 堆

题目

url:https://leetcode.com/problems/kth-largest-element-in-an-array/

215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.

分析

用数据结构 Head（堆）来实现

堆：完全二叉树，常常用数组表示

用数组表示一棵树时，如果数组中节点的索引位x，则
a、它的父节点的下标是：(x-1)/2；
b、它的左子节点的下标为：2x + 1；
c、它的右子节点的下标是：2x + 2；

堆的数组实现：https://www.cnblogs.com/g177w/p/8469399.html

Java解法

class Solution {
    class Node {
        private int data;
        public Node(int d) {
            this.data = d;
        }
        public int getValue() {
            return this.data;
        }
        public void setValue(int d) {
            this.data = d;
        }
    }
    class Head {
        private Node[] headArray;
        private int maxSize;
        private int currentSize;
        public Head(int maxSize) {
            this.maxSize = maxSize;
            currentSize = 0;
            headArray = new Node[maxSize];
        }
        public boolean isEmpty() {
            return 0 == currentSize;
        }
        public boolean insert(int d) {
            if (this.currentSize == this.maxSize) {
                return false;
            }
            Node node = new Node(d);
            headArray[currentSize] = node;
            trickleUp(currentSize++);
            return true;
        }
        public void trickleUp(int index) {
            int parentIndex = (index - 1) / 2;
            Node node = headArray[index];
            while (index > 0 && 
                   headArray[parentIndex].getValue() < node.getValue()) {
                headArray[index] = headArray[parentIndex];
                index = parentIndex;
                parentIndex = (index - 1) / 2;
            }
            headArray[index] = node;
        }
        public Node remove() {
            Node root = headArray[0];
            headArray[0] = headArray[--currentSize];
            trickleDown(0);
            return root;
        }
        public void trickleDown(int index) {
            int largeChild;
            Node node = headArray[index];
            while (index < currentSize/2) {
                int leftChild = 2 * index + 1;
                int rightChild = 2 * index +2;
                if (rightChild < currentSize && headArray[leftChild].getValue()
                    < headArray[rightChild].getValue()) {
                    largeChild = rightChild;
                } else {
                    largeChild = leftChild;
                }
                if (node.getValue() >= headArray[largeChild].getValue()) {
                    break;
                }
                headArray[index] = headArray[largeChild];
                index = largeChild;
            }
            headArray[index] = node;
        }
        public boolean change(int index, int newValue) {
            if (index < 0 || index > currentSize) {
                return false;
            }
            int oldValue = headArray[index].getValue();
            headArray[index].setValue(newValue);
            if (oldValue < newValue) {
                trickleUp(index);
            } else  {
                trickleDown(index);
            }
            return true;
        }
        public void displayHead() {
             System.out.print("headArray:");
             for (int i = 0; i < currentSize; i++) {
                 if (headArray[i] != null)
                     System.out.print(headArray[i].getValue()+"  ");
                 else
                     System.out.print("--");
             }
             System.out.println("");
             int nBlanks = 32;
             int itemsPerrow = 1;
             int column = 0;
             int j = 0;
             String dots = "........................";
             System.out.println(dots + dots);
             while (currentSize > 0){
                 if (column == 0)
                     for (int i = 0; i < nBlanks; i++) {
                         System.out.print(" ");
                     }
                 System.out.print(headArray[j].getValue());
                 if (++ j == currentSize)
                     break;
                 if (++ column == itemsPerrow){
                     nBlanks /= 2;
                     itemsPerrow *= 2;
                     column = 0;
                     System.out.println();
                 }
                 else
                     for (int i = 0; i < nBlanks * 2 - 2; i++) 
                         System.out.print(' ');
             }
             System.out.println("\n"+dots + dots);
        }
    }
    
    public int findKthLargest(int[] nums, int k) {
        Head head = new Solution().new Head(nums.length);
        for (int x : nums) {
            head.insert(x);
        }
        for (int i=0; i<k-1; ++i) {
            head.remove();
        }
        int ret = head.remove().getValue();
        return ret;
    }
}

Python解法

1
2

h index ii

发表于 2016-03-27

算法：

url：https://leetcode.com/problems/h-index-ii/

题目

Given an array of citations sorted in ascending order (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

Example:

Input: citations = [0,1,3,5,6]
Output: 3 
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had 
             received 0, 1, 3, 5, 6 citations respectively. 
             Since the researcher has 3 papers with at least 3 citations each and the remaining 
             two with no more than 3 citations each, her h-index is 3.
Note:

If there are several possible values for h, the maximum one is taken as the h-index.

Follow up:

This is a follow up problem to H-Index, where citations is now guaranteed to be sorted in ascending order.
Could you solve it in logarithmic time complexity?

思路分析

[0,1,3,5,6]

数组长度 n，存在一个元素 h，使得 n 中有 h个元素大于等于h，其他（n-h）个元素 < h；

求h？

数组是有序的递增数组

遍历 arr，存在 arr[i], 使得 n-i == arr[i]

Java解法

class Solution {
    public int hIndex(int[] citations) {
        for(int i=citations.length-1; i>=0; --i) {
            if(citations[i] == citations.length-i) {
                return citations[i];
            }
        }
        return 0;
    }
}

public int hIndex(int[] citations) {
        int l = 1, r = citations.length;
        int ans = 0;
        while(l <= r){
            int m = l + ((r - l)>>1);
            int p = citations[citations.length - m];
            if(m == p){
                return m;
            }
            if(m > p){
                r = m - 1;
            }
            else{
                ans = Math.max(ans, m);
                l = m + 1;
            }
        }
        return ans;
    }
}

Python解法

Binary Tree Right Side View

发表于 2016-03-26

算法：二叉树广度优先遍历 BFS

URL：https://leetcode.com/problems/binary-tree-right-side-view/

题目

Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example:
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

Input: [1,2,3,null,5,null,4,null,null,8]
Output: [1, 3, 4, 8]
Explanation:

       1            <---
     /   \
    2     3         <---
     \     \
      5     4       <---
     /
    8               <---

分析

使用层序遍历（level traversal），即广度优先搜索 —— 借助Queue

难点是标注每一层，来标注每层的最后一个节点

当前层节点总数：count1，当前访问到节点数 i

下一层几点总数：count2

Java解法

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        return BFS(root);
    }
    public List<Integer> BFS(TreeNode root) {
        List<Integer> retList = new ArrayList<Integer>();
        if(null == root) return retList;
        int count1=1, count2=0;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()) {
            for(int i=0; i<count1; ++i) {
                TreeNode tn = queue.poll();
                if(null != tn) {
                    if (i == count1-1) {
                        retList.add(tn.val);
                    }
                    if(null != tn.left) {
                        queue.add(tn.left);
                        count2++;
                    }
                    if (null != tn.right) {
                        queue.add(tn.right);
                        count2++;
                    }
                }
            }
            count1 = count2;
            count2 = 0;
        }
        return retList;
    }
}

结果

Runtime: 1 ms, faster than 98.22% of Java online submissions for Binary Tree Right Side View.

Memory Usage: 36.3 MB, less than 100.00% of Java online submissions for Binary Tree Right Side View.

1次AC，Niubility

Python解法

1
2

Binary Tree Maximum Path Sum

发表于 2016-03-25

算法：二叉树 + 动态规划

url：https://leetcode.com/problems/binary-tree-maximum-path-sum/

题目

124. Binary Tree Maximum Path Sum
Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6
Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

分析：

不要求最大值的路径，只要求最大值

Java解法

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
class Solution {
    int ret = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        return maxSum(root);
    }
    public int maxSum(TreeNode root) {
        if (null == root) return 0;
        int l = Math.max(0, maxSum(root.left));
        int r = Math.max(0, maxSum(root.right));
        int sum = l + r + root.val;
        ret = Math.max(ret, sum);
        return Math.max(l, r) + root.val;
    }
}

算法分类：Stack

题目

Java解法

Python解法

算法：二叉搜索树

题目

Java解法

Python解法

url：

题目：

Java 解法：

Python解法：

算法：二叉搜索树， 深度优先搜索

题目

Java解法

Python解法

算法：单链表反转

题目

Java解法

Python解法

算法：动态规划

题目

Java解法

Python解法

算法：Heap 堆

题目

分析

Java解法

Python解法

算法：

题目

思路分析

Java解法

Python解法

算法：二叉树广度优先遍历 BFS

题目

Java解法

Python解法

算法：二叉树 + 动态规划

题目

Java解法

算法：二叉搜索树，深度优先搜索