Boundary of Binary Tree

http://www.lintcode.com/zh-cn/problem/boundary-of-binary-tree/

import java.util.ArrayList;
import java.util.List;

/**
 * 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: a TreeNode
     * @return: a list of integer
     */
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        // write your code here
        List<Integer> res = new ArrayList<>();
        if (root != null) {
            List<TreeNode> leftList = new ArrayList<>();
            List<TreeNode> bottomList = new ArrayList<>();
            List<TreeNode> rightList = new ArrayList<>();
            treeWalkLeft(root, leftList);
            treeWalkRight(root, rightList);
            treeWalkBottom(root, bottomList);
            for (int i = 0; i < leftList.size(); i++) {
                TreeNode treeNode = leftList.get(i);
                res.add(treeNode.val);
            }
            for (int i = 0; i < bottomList.size(); i++) {
                TreeNode treeNode = bottomList.get(i);
                res.add(treeNode.val);
            }
            for (int i = rightList.size() - 1; i >= 0; i--) {
                TreeNode treeNode = rightList.get(i);
                if (!leftList.contains(treeNode)) {
                    res.add(treeNode.val);
                }
            }
        }
        return res;
    }

    private void treeWalkBottom(TreeNode root, List<TreeNode> bottomList) {
        if (root == null) {
            return;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        if (left == null && right == null) {
//            是叶子节点
            bottomList.add(root);
        }
        treeWalkBottom(left, bottomList);
        treeWalkBottom(root.right, bottomList);

    }

    private void treeWalkRight(TreeNode root, List<TreeNode> rightList) {
        if (root == null) {
            return;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        if (left == null && right == null) {
//            是叶子节点
            return;
        } else if (right != null) {
            rightList.add(root);
            treeWalkRight(root.right, rightList);
        } else if (left != null) {
            rightList.add(root);
            treeWalkRight(left, rightList);
        }

    }

    private void treeWalkLeft(TreeNode root, List<TreeNode> leftList) {
        if (root == null) {
            return;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        if (left == null && right == null) {
//            是叶子节点
            return;
        } else if (left != null) {
            leftList.add(root);
            treeWalkLeft(root.left, leftList);
        } else if (right != null) {
            leftList.add(root);
            treeWalkLeft(right, leftList);
        }
    }
}