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;
    }
}

Sum Root to Leaf Numbers leetcode

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

用递归的方法来做, 把根节点到叶子节点所有值加起来, 递归条件是把当前的sum*10 加上子节点的值进行下一轮递归

结束条件是到子节点是空的时候就返回0
算法的本质是一次先序遍历，所以时间是O(n)，空间是栈大小，O(logn)。

public class Solution {
    public int sumNumbers(TreeNode root) {
        return helper(root, 0);    
    }
    public int helper(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return sum * 10 + root.val;
        }
        int left = helper(root.left, sum*10 + root.val);
        int right = helper(root.right, sum*10 + root.val);
        return left + right;
    }
}

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);
    }
}

Gray Code leetcode

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

这道题最后返回的是格雷码的二进制对应的十进制数...首先看下格雷码定义(我看了十分钟才看明白这包涵深深恶意的定义)

如果格雷码从n位(2^n 个码)变为n+1位(2^n+1)个码:

(n+1)位格雷码中的前2^n个码字等于n位格雷码的码字，按顺序书写，加前缀0 
(n+1)位格雷码中的后2^n个码字等于n位格雷码的码字，按逆序书写，加前缀1。

n = 0时，[0]

n = 1时，[0,1]

n = 2时，[00,01,11,10]

n = 3时，[000,001,011,010,110,111,101,100]

所以从头开始构建, n每增加1 就把当前2^n个结果逆序并且在前面+1 再加到结果中得到2^n+1个结果

1 << n 二进制的位运算: 1 向左移动n位 >>是向右移动
算法复杂度是O(2+2^2+...+2^n-1)=O(2^n)，所以是指数量级的，因为是结果数量无法避免。空间复杂度则是结果的大小，也是O(2^n)。

public class Solution {
    /**
     * @param n a number
     * @return Gray code
     */
    public ArrayList<Integer> grayCode(int n) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        
        res.add(0);
        if (n == 0) {
            return res;
        }
        res.add(1);
        for (int j = 2; j <=n; j++) {
            int size = res.size();
            int addnum = 1 << j-1;
            for (int i = size - 1; i >= 0; i--) {
                res.add(addnum + res.get(i));
            }
        }
        return res;
    }
}

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;    
    }
    
    
}

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;
        
    }
}