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


  • 15
    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;

    C++

    class Solution {
    public:
        vector<int> boundaryOfBinaryTree(TreeNode* root) {
            vector<int> bounds;
            if (root) {
                bounds.push_back(root->val);
                getBounds(root->left, bounds, true, false);
                getBounds(root->right, bounds, false, true);
            }
            return bounds;
        }
    
    private:
        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);
        }
    };
    

    Java

    public class Solution {
        public List<Integer> boundaryOfBinaryTree(TreeNode root) {
            List<Integer> res = new ArrayList<Integer>();
            if (root != null) {
                res.add(root.val);
                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

    @alexander

    Nice!


  • 0

    @zzhai Thanks!


Log in to reply
 

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