PreOrder O(n) check everynode only once


  • 0
    F
    // preorder property
        boolean seeLeaf = false;
        public List<Integer> boundaryOfBinaryTree(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            if (root == null) return res;
            res.add(root.val);
            if (root.left != null) {
                preOrder(root.left, res);
            }
            List<Integer> revRes = new ArrayList<>();
            seeLeaf = false;
            if (root.right != null) {
                revPreOrder(root.right, revRes);
            }
            for (int i = revRes.size()-1; i >= 0; i--) {
                res.add(revRes.get(i));
            }
            return res;
        }
        
        private void preOrder(TreeNode root, List<Integer> res) {
            if (root.left == null && root.right == null) {
                res.add(root.val);
                seeLeaf = true;
                return;
            }
            if (!seeLeaf) res.add(root.val);
            if (root.left != null) {
                preOrder(root.left, res);
            }
            if (root.right != null) {
                 preOrder(root.right, res);
            }
        }
        private void revPreOrder(TreeNode root, List<Integer> res) {
            if (root.left == null && root.right == null) {
                res.add(root.val);
                seeLeaf = true;
                return;
            }
            if (!seeLeaf) res.add(root.val);
            if (root.right != null) {
                revPreOrder(root.right, res);
            }
            if (root.left != null) {
                 revPreOrder(root.left, res);
            }
        }

  • 0
    B

    I think this would not work .
    Please try following test cases:
    Preorder- 1 2 4 5 6 7 3
    Postorder- 4 6 7 5 2 3 1


  • 0
    F
    This post is deleted!

  • 0
    F

    @bitlearn By my algorithm, it return [1,2,4,6,7,3]. Actually, in my algorithm, the postOrder is not standard, This name can cause confusion. The postOrder of my algorithm is to check root firstly, then check root.right check root.left, you can think it equals with preOrder on the tree which is generated by that you exchange left/right subtree in originally tree recursively.

    Other thing I want to say is that I think this problem is to test the preOrder property which is before reaching
    first leaf, the nodes you checked are left boundary nodes in this problem.

    No matter any order (pre, post, in) you check tree, the leafs you checked is from left to right.

    For right boundary, you could image that you exchange the left, right subtree recursively, then preOrder check on this changed tree can give you the right boundary but it is reversed.


Log in to reply
 

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