[Java] [C++] Clean Code (1 Pass perorder postorder hybrid)

  • 20
    1. node.left is left bound if node is left bound;
      node.right could also be left bound if node is left bound && node has no right child;
    2. Same applys for right bound;
    3. if node is left bound, add it before 2 child - pre order;
      if node is right bound, add it after 2 child - post order;
    4. A leaf node that is neither left or right bound belongs to the bottom line;


    class Solution {
        vector<int> boundaryOfBinaryTree(TreeNode* root) {
            vector<int> bounds;
            if (root) {
                getBounds(root->left, bounds, true, false);
                getBounds(root->right, bounds, false, true);
            return bounds;
        void getBounds(TreeNode* node, vector<int>& res, bool lb, bool rb) {
            if (!node)  return;
            if (lb) res.push_back(node->val);
            if (!lb && !rb && !node->left && !node->right)  res.push_back(node->val);
            getBounds(node->left, res, lb, rb && !node->right);
            getBounds(node->right, res, lb && !node->left, rb);
            if (rb) res.push_back(node->val);


    public class Solution {
        public List<Integer> boundaryOfBinaryTree(TreeNode root) {
            List<Integer> res = new ArrayList<Integer>();
            if (root != null) {
                getBounds(root.left, res, true, false);
                getBounds(root.right, res, false, true);
            return res;
        private void getBounds(TreeNode node, List<Integer> res, boolean lb, boolean rb) {
            if (node == null) return;
            if (lb) res.add(node.val);
            if (!lb && !rb && node.left == null && node.right == null) res.add(node.val);
            getBounds(node.left, res, lb, rb && node.right == null);
            getBounds(node.right, res, lb && node.left == null, rb);
            if (rb) res.add(node.val);

  • 0



  • 0

    @zzhai Thanks!

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.