One pass preorder-postorder hybrid algorithm in Java.


  • 1
    Y
    public class Solution {
        public List<Integer> boundaryOfBinaryTree(TreeNode root) {
            List<Integer> result = new ArrayList<>();
            if (root == null) {
                return result;
            }
            
            result.add(root.val);
            preorder(root.left, true, result);
            postorder(root.right, true, result);
            
            return result;
        }
        
        private void preorder(TreeNode node, boolean isBoundary, List<Integer> visitor) {
            if (node == null) {
                return;
            }
            if (isBoundary || isLeaf(node)) {
                visitor.add(node.val);
            } 
            
            if (node.left != null) {
                preorder(node.left, isBoundary, visitor);
                preorder(node.right, false, visitor);
            } else {
                preorder(node.right, isBoundary, visitor);
            }
    
            
        }
        
        private void postorder(TreeNode node, boolean isBoundary, List<Integer> visitor) {
            if (node == null) {
                return;
            }
            if (node.right != null) {
                postorder(node.left, false, visitor);
                postorder(node.right, isBoundary, visitor);
            } else {
                postorder(node.left, isBoundary, visitor);
            }
           
            
            if (isBoundary || isLeaf(node)) {
                visitor.add(node.val);
            } 
            
        }
        
        private boolean isLeaf(TreeNode node) {
            return node.left == null && node.right == null;
        }
    }
    

  • 0
    I

    Nice Solution! Great handling of isBoundary variable. I was doing similar thing but wasn't able to handle postorder part properly.


Log in to reply
 

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