Binary Tree Postorder Traversal – leetcode

Question:
Given a binary tree, return the postorder traversal of its nodes’ values.

Thought:
Use a stack, and a cur value to see if we have reached the left node,then we pop from the stack, for inorder, we can just visit the node, but for post order, we need to check if the node has right child. If it has right child, null out its right child, push back to stack, and make the node equals its right child.

    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack= new Stack<>();
        List<Integer> result = new ArrayList<>();
        TreeNode cur= root;
        while(!stack.isEmpty()||cur!=null){
            if(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }else{
                cur=stack.pop();
                if(cur.right!=null){
                    TreeNode right=cur.right;
                    cur.right=null;
                    stack.push(cur);
                    cur=right;
                }else{
                    result.add(cur.val);
                    cur=cur.right;//bug..
                }
            }
        }
        return result;
    }

One Edit Distance – leetcode

Question:
Given two string, check to see if they are 1 edit distance apart from each other.

Thought:
Approach 1, we can use DP to see if they are 1 distance away, solution will be the same as Edit distance.

Approach 2, since this is to check if they are 1 edit distance away, we can start by check the length, if length is larger than 2, return false. If length is the same, we could only allow one character to be different. If length diff is 1, we check if we can insert one character to make them same.

To check that, we simply iterate two string, if one of the character is not matching, the rest characters has to match.

Code:

  public boolean isOneEditDistance (String s, String t) {
        int len1 = s.length ();
        int len2 = t.length ();
        int diff = Math.abs (len1 - len2);
        if (diff > 1) {
            return false;
        }
        if (diff == 1) {
            return isInsert (s, t);
        } else {
            return isReplace (s, t);
        }
    }

    private boolean isReplace (String s, String t) {
        int count = 0;
        for (int i = 0; i < s.length (); i++) {
            char c = s.charAt (i);
            char c2 = t.charAt (i);
            if (c != c2)
                count++;
        }
        return count == 1;
    }

    private boolean isInsert (String s, String t) {
        if (s.length () < t.length ())
            return isInsert (t, s);
        for (int i = 0; i < t.length (); i++) {
            if (s.charAt (i) == t.charAt (i)) {
                continue;
            } else {
                if( t.charAt (i) != s.charAt (i + 1)){
                    return false;
                }
            }
        }
        return true;
    }

Java I/O

1. To handle a large file.

FileInputStream fis= new FileInputStream("file_location");
//approach 1
BufferedReader br = new BufferedReader(new InputStreamReader(fis, encoding));
br.readLine();
//approach 2
Scanner scan= new Scanner(fis, "UTF-8");
scan.hasNext();
scan.next();

FileOutputStream fos= new FileOutputStream("file_location");
BufferedWriter bw= new BufferedWritter(new OutputStreamWritter(fos,encoding));
bw.write();

fis.close();
fos.close();

Note: if the file is very large, as long as we read line then write it to the file, it will not stay in memory, so we should be good for that.

Read also provide a overloading method to take a char array so you can make it read a reasonable size.

If you want to know the line number of the file and doesn’t care about the file content, then use scanner. See approach 2.