• [ ] #100, 572

110. Balanced Binary Tree

• can use height == 1 to indicate that the sub-tree is no longer balanced
  • no need to use a Pair<Boolean, Integer> to store both the height and the result (balance-or-not)
• haven't found a good way to do iterative version, as it is kind of hard to backtrack

class Solution {

    public boolean isBalanced(TreeNode root) {
        return (heightCheck(root) != -1);
    }

    private int heightCheck(TreeNode root) {
        if (root == null) return 0;
        
        int left = heightCheck(root.left);
        if (left == -1) return -1;
        int right = heightCheck(root.right);
        if (right == -1) return -1;

        if (Math.abs(left - right) > 1) return -1;

        return Math.max(left, right) + 1;

    }
}

(Version using Pair<Boolean, Integer>)

class Solution {

    public boolean isBalanced(TreeNode root) {
        Pair<Boolean, Integer> result = heightCheck(root);
        return result.getKey();
    }

    private Pair<Boolean, Integer> heightCheck(TreeNode root) {
        if (root == null) return new Pair<>(true, 0);
        
        Pair<Boolean, Integer> left = heightCheck(root.left);
        if (!left.getKey()) return new Pair<Boolean, Integer>(false, -1);
        Pair<Boolean, Integer> right = heightCheck(root.right);
        if (!right.getKey()) return new Pair<Boolean, Integer>(false, -1);

        if (Math.abs(left.getValue() - right.getValue()) > 1) return new Pair<Boolean, Integer>(false, -1);

        return new Pair<Boolean, Integer>(true, Math.max(left.getValue(), right.getValue()) + 1);

    }
}

257. Binary Tree Paths

• pre-order traversal
• backtrack 回溯
  • can use String / StringBuilder or List<Node>
    • Note that re-using StringBuilder requires backtracking (or just new another for one of the two sub trees)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private List<String> res = new ArrayList<>();

    private void pathHelper(TreeNode root, String path) {
        if (root == null) return;

        // update path
        path += root.val;

        // leaf
        if (root.left == null && root.right == null) {
            res.add(path);
            return;
        }

        path += "->";
        if (root.left != null) pathHelper(root.left, path);
        if (root.right != null) pathHelper(root.right, path);
    }

    public List<String> binaryTreePaths(TreeNode root) {
        pathHelper(root, "");
        return res;
    }
}

alternatively, using StringBuilder

class Solution {
    private List<String> res = new ArrayList<>();

    private void pathHelper(TreeNode root, StringBuilder path) {
        if (root == null) return;

        // update path
        path.append(root.val);

        // leaf
        if (root.left == null && root.right == null) {
            res.add(path.toString());
            return;
        }

        path.append("->");
        pathHelper(root.left, new StringBuilder(path));
        pathHelper(root.right, path);
    }

    public List<String> binaryTreePaths(TreeNode root) {
        pathHelper(root, new StringBuilder());
        return res;
    }
}

一个奇技淫巧的做法，记录和重置长度（相当于回溯），重复使用StringBuilder

class Solution {
    
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> ans = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        path(root, sb, ans);
        return ans;
    }

    void path(TreeNode root, StringBuilder sb, List<String> ans) {

        if(root == null) {
            return;
        }

        **int len = sb.length();**
        sb.append(root.val);

        if(root.left == null && root.right == null) {
            ans.add(sb.toString());

        } else {
            sb.append("->");
            path(root.left, sb , ans);
            path(root.right, sb, ans);
        }
        // recycle the StringBuilder
        // to the length before adding current node's value
        **sb.setLength(len);**
    }
}

// alternatively, can reuse only in one side
	//...
				} else {
            sb.append("->");
            path(root.left, new StringBuilder(sb) , ans);
            path(root.right, sb, ans);
        }
        // no need to set length anymore
        // sb.setLength(len);

Iterative version

• the idea is keeping two stacks - one for the node, one for the corresponding path (string) for that node
  • for Java, can use a stack of Object and push both node and path to the same stack
• generally, iterative version is not easy for backtracking

class Solution {
    private List<String> res = new ArrayList<>();

    public List<String> binaryTreePaths(TreeNode root) {
        Deque<Object> st = new ArrayDeque<>();
        if (root == null) return res;

        st.push(root);
        st.push(String.valueOf(root.val));

        while (!st.isEmpty()) {
            String path = (String) st.poll();
            TreeNode cur = (TreeNode) st.poll();
            
            if (cur.left == null && cur.right == null) {
                res.add(path);
            } else {
                if (cur.left != null) {
                    st.push(cur.left);
                    st.push(path + "->" + cur.left.val);
                }
                if (cur.right != null) {
                    st.push(cur.right);
                    st.push(path + "->" + cur.right.val);
                }
            }
        }

        return res;
    }
}

404. Sum of Left Leaves