Binary Tree Postorder Traversal leetcode

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

postorder： 左－右－中

public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (root == null){
            return result;
        }
        ArrayList<Integer> left = postorderTraversal(root.left);
        ArrayList<Integer> right = postorderTraversal(root.right);
        result.addAll(left);
        result.addAll(right);
        result.add(root.val);
        return result;
        
    }
}

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        helper(res, root);
        return res;
    }
    public void helper(List<Integer> res, TreeNode root) {
        if (root == null) {
            return;
        }
        helper(res, root.left);
        helper(res, root.right);
        res.add(root.val);
    }
}
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        TreeNode pre = null;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode peak = stack.peek();
                if (peak.right != null && pre != peak.right) {///如果当前栈顶元素的右结点存在并且还没访问过（也就是右结点不等于上一个访问结点）就访问右结点 /
                    root = peak.right;
                } else {////如果栈顶元素右结点是空或者已经访问过，那么说明栈顶元素的左右子树都访问完毕 需要把栈顶元素加入结果并且回溯上一层
                    stack.pop();
                    res.add(peak.val);
                    pre = peak;
                }
                
            }
        }
        return res;
    }
}

Flatten Binary Tree to Linked List leetcode

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

这道题题意就是把树变成linkedlist 但是要以只有右子树的树形式表示出来
用先序遍历, 遍历到的值作为便利到的前一个点的右子树, 前一个点的左子树设为空.
因为递归右子树是在递归左子树之后, 所以root.right会发生变化, 所以root.right要单独存储起来. 便利一次 时间为O(n).

非递归解法就是遇到右子树就入栈， 然后把左子树变成自己的右子树， 左子树设空。 如果没有左子树了， 就从栈里拿出一个当当前node的右子树。

public class Solution {
    public void flatten(TreeNode root) {
        ArrayList<TreeNode> res = new ArrayList<TreeNode>();
        res.add(null);
        helper(res, root);
    }
    public void helper(ArrayList<TreeNode> res, TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode right = root.right;
        if (res.get(0) != null) {
            res.get(0).right = root;
            res.get(0).left = null;
        }
        res.set(0, root);
        helper(res, root.left);
        helper(res, right);
    }
}
//非递归解法 推荐
public class Solution {
    public void flatten(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
        while(p != null || !stack.isEmpty()) {
            if (p.right != null) {
                stack.push(p.right);
            }
            if (p.left != null) {
                p.right = p.left;
                p.left = null;
            } else if (!stack.isEmpty()) {
                TreeNode tem = stack.pop();
                p.right = tem;
            }
            p = p.right;
        }
    }
}

Same Tree leetcode

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

这道题是树的题目，属于最基本的树遍历的问题。问题要求就是判断两个树是不是一样，基于先序，中序或者后序遍历都可以做完成，因为对遍历顺序没有要求。这里我们主要考虑一下结束条件，如果两个结点都是null，也就是到头了，那么返回true。如果其中一个是null，说明在一棵树上结点到头，另一棵树结点还没结束，即树不相同，或者两个结点都非空，并且结点值不相同，返回false。最后递归处理两个结点的左右子树，返回左右子树递归的与结果即可。这里使用的是先序遍历，算法的复杂度跟遍历是一致的，如果使用递归，时间复杂度是O(n)，空间复杂度是O(logn)。

reference:http://codeganker.blogspot.com/2014/04/balanced-binary-tree-leetcode.html

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {//p或者q只有一方是null
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Minimum Depth of Binary Tree leetcode

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

如果一个node的左儿子为空 右儿子不空 从root 到左儿子的路径不算是minimum depth
因为左儿子不算这个node的leaf node
所以要比最大深度那道题要多一个判断
如果左儿子空返回右儿子的deepth 右儿子空返回左儿子deepth

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: An integer.
     */
    public int minDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if (left == 0) {
            return right + 1;
        }
        if (right == 0) {
            return left + 1;
        }
        return Math.min(left, right) + 1;
    }
}

非递归的做法:

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: An integer.
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int res = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null) {
                    return res + 1;//node已经算入了 所以要+1 
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            res += 1;
        }
        return res;
    }
}

Path Sum leetcode

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

递归(分治)方法来做，递归条件是看左子树或者右子树有没有满足条件的路径，也就是子树路径和等于当前sum减去当前节点的值。结束条件是如果当前节点是空的，则返回false，如果是叶子，那么如果剩余的sum等于当前叶子的值，则找到满足条件的路径，返回true。算法的复杂度是输的遍历，时间复杂度是O(n)，空间复杂度是O(logn)。

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null && root.val == sum) {
            return true;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

Convert Sorted Array to Binary Search Tree leetcode

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
选择中点构造根节点然后递归构造左子树和右子树
因为递归时候要记录一个起始位置一个终止位置， 所以构造一个helper函数
注意中点被构造成root 所以递归带入是mid-1 和mid+1 所以边界条件是start > end
时间复杂度还是一次树遍历O(n)，空间复杂度是栈空间O(logn)加上结果的空间O(n)，所以额外空间是O(logn)，总体是O(n)。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        if (num == null || num.length == 0){
            return null;
        }
        return helper(num, 0, num.length - 1);
    }
    private TreeNode helper(int[] num, int start, int end){
        if (start > end){//因为是mid-1 和mid+1 所以到最后会出现start<end 而不是等于
            return null;
        }
        int mid = (start + end)/2;
        TreeNode node = new TreeNode(num[mid]);
        node.left = helper(num, start, mid-1);
        node.right = helper(num, mid + 1, end);
        return node;
    }
}

Merge k Sorted Lists leetcode

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
用分治法的mergesort的思想 把lists分成小list 最后合并
merge的方法就是之前merge 2 sorted list的方法

时间复杂度O(nlog(n)) 计算方法用主定理

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
  
        if (lists.length == 0 || lists == null){
            return null;
        }
        return sort(lists, 0, lists.length - 1);
    }
    private ListNode sort(ListNode[] lists, int start, int end){
        if (start == end){
            return lists[start];
        }
        int mid = (start + end) / 2;
        ListNode left = sort(lists, start, mid);
        ListNode right = sort(lists, mid + 1, end);
        return merge(left, right);
    }
    private ListNode merge(ListNode left, ListNode right){
        ListNode dummy = new ListNode(0);
        ListNode point = dummy;
        while (left != null && right != null){
            if (left.val < right.val){
                point.next = left;
                left = left.next;
            } else {
                point.next = right;
                right = right.next;
            }
            point = point.next;
        }
        if (left != null){
            point.next = left;
        } else {
            point.next = right;
        }
        return dummy.next;
    }
}

Binary Tree Inorder Traversal leetcode

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

Inorder: return [1,3,2]. 左中右

addAll 是因为arraylist result 里面应该添加int

第一种是递归的算法，时间复杂度是O(n), 而空间复杂度则是递归栈的大小，即O(logn)。

第二种是迭代的算法， 用栈来实现。 时间复杂度是O(n), 空间O(logn)
第三种是分治算法

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        helper(res, root);
        return res;
    }
    public void helper(List<Integer> res, TreeNode root) {
        if (root == null) {
            return;
        }
        helper(res, root.left);
        res.add(root.val);
        helper(res, root.right);
    }
}
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root= root.left;
            } else {
                root = stack.pop();
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }
}
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        List<Integer> left = inorderTraversal(root.left);
        List<Integer> right = inorderTraversal(root.right);
        res.addAll(left);
        res.add(root.val);
        res.addAll(right);
        return res;    
    }
    
    
}

Lowest Common Ancestor lintcode

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

Example

        4

    /     \

  3         7

          /     \

        5         6

For 3 and 5, the LCA is 4.

For 5 and 6, the LCA is 7.

For 6 and 7, the LCA is 7.
这道题还是用分治法， 从最底下往上遍历，当找到一个所给node，向上传递node， 如果没找到就传递null。 上一层的parent会check自己的左右子树是否都有返回值，a.如果都有值那么这个node就是LCA， 向上传递这个node一直到根节点。b. 只有一个子树有值， 那么向上传递这个子树。c.若果左右都没有， 向上传递null

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of the binary search tree.
     * @param A and B: two nodes in a Binary.
     * @return: Return the least common ancestor(LCA) of the two nodes.
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
        if (root == null){
            return null;
        }
        if (root == A || root == B){
            return root;//当找到一中一个node， 向上传递这个node
        }
        TreeNode left = lowestCommonAncestor(root.left, A, B);
        TreeNode right = lowestCommonAncestor(root.right, A, B);
        if (left != null && right != null){//check左右，如果左右分别包含两个node则这个root就是LCA， 向上传递这个node
            return root;
        } else if (left != null){//只有左边有node，向上传递此node
            return left;
        } else if (right != null){
            return right;
        } else{//左右边都没有node 传递null
            return null;
        }
    }
}

Binary Tree Maximum Path Sum leetcode

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

这道题包涵root在内的最大值有四种情况：
 1.root本身（可能有负数存在的情况）
 2. root+左子树
 3.root+ 右子树
 4.root + 左子树 + 右子树 解题
因为需要一个位置来存储最大值， 所以新建一个helper函数 把最大值存入一个数组里， 这样便利完整个树之后最大值久得到了。
这里注意result的初始值应该是Integer.MIN_VALUE

解题思路就是找到最大的一条更新到result[0]里面 （java无法按引用传，就只能建立一个数组）
1,2,3 三部需要用来当前root分支的最大值（4情况不算是root的分支了）， 所以要传回去

算法的本质还是一次树的遍历，所以复杂度是O(n)。而空间上仍然是栈大小O(logn)。

public class Solution {
    public int maxPathSum(TreeNode root) {
        int[] result = new int[1];
        result[0] = Integer.MIN_VALUE;
        helper(result, root);
        return result[0];
    }
    public int helper(int[] result, TreeNode root){
        if (root == null){
            return 0;
        }
        //divide
        int left = helper(result, root.left);
        int right = helper(result, root.right);
        //Conquer
        int max = Math.max(root.val, Math.max(root.val + left, root.val + right));//找1,2,3的最大值返回
        result[0] = Math.max(result[0], Math.max(max, root.val + left + right));//把4步里的最大值和result[0]比较，返回最大的为result[0]
        return max;
    }
}

Balanced Binary Tree leetcode

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

这道题跟之前一道是一样的 就是找binary tree的深度，用分治法解题。但是要返回的是Boolean值 所以就写一个helper程序 在树平衡时候返回深度 不平衡就返回-1 . 然后用Boolean判定最后返回是否为-1

算法的时间是一次树的遍历O(n)，空间是栈高度O(logn)。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        return checkBalance(root) != -1;
    }
    public int checkBalance(TreeNode root){
        if (root == null){
            return 0;
        }
        int left = checkBalance(root.left);
        int right = checkBalance(root.right);
        if (left == -1|| right == -1|| Math.abs(left - right) > 1){
            return -1;
        }//如果left或者right不平衡就网上返回-1；
        return Math.max(left, right) + 1;
    }
}

Maximum Depth of Binary Tree leetcode & Divide and conquer模板

Divide and Conquer 模板

public class Solution {
    public ResultType traversal(TreeNode root) {
        // null or leaf
        if (root == null) {
            // do something and return;
        }

        // Divide
        ResultType left = traversal(root.left);
        ResultType right = traversal(root.right);

        // Conquer
        ResultType result = Merge from left and right.
        return result;
    }
}

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

public class Solution {
    public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1//深度=子数深度+1;
    }
}

//非递归解法 BFS
public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int res = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            res += 1;
        }
        return res;
    }
}

Binary Tree Preorder Traversal leetcode

Given a binary tree, return the preorder traversal of its nodes' values.

Example

Note

Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].
preorder 左 －－中－－ 右

第一种方法：迭代iteratively算法的时间复杂度是O(n), 而空间复杂度则是递归栈的大小，即O(logn)

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                res.add(root.val);
                root = root.left;
            } else {
                root = stack.pop();
                root = root.right;
            }
        }
        return res;
    }
}

第二种方法： 递归（Recursive）算法的时间复杂度是O(n), 而空间复杂度则是递归栈的大小，即O(logn)

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

第三种 分治(Divide & Conquer)

Generally, D&C questions would do 2 things at same time:

1. Divide – For binary tree, it mean solve left child, and solve right child
2. Conquer – return result value

public class Solution {
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (root == null){
            return result;
        }
        //divide
        ArrayList<Integer> left = preorderTraversal(root.left);
        ArrayList<Integer> right = preorderTraversal(root.right);
        // Conquer
        result.add(root.val);
        result.addAll(left);//用addall方法是因为left类型是arraylist不是int
        result.addAll(right);
        return result;
        
    }
}