class Solution {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>(); 
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        recur(root, sum);
        return res;
    }
    void recur(TreeNode root, int tar) {
        if(root == null) return;
        path.add(root.val);
        tar -= root.val;
        if(tar == 0 && root.left == null && root.right == null)
            res.add(new LinkedList(path));
        recur(root.left, tar);
        recur(root.right, tar);
        path.removeLast();
    }
}

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> path=new ArrayList<>();
    if(root==null){return path;}
    Stack<TreeNode> s=new Stack<>();
    s.push(root);
    while(!s.isEmpty()){
        TreeNode curNode=s.pop();
        path.add(curNode.val);
        
        if(curNode.right!=null) s.push(curNode.right);
        if(curNode.left!=null) s.push(curNode.left);
    }
    return path;
    }
}

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preorder(root, res);
        return res;
    }

    public void preorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }
}

public int[] levelOrder(TreeNode root) {
    if(root==null) return new int[0];
    Queue<TreeNode> q=new LinkedList<>();
    q.add(root);
    List<Integer> res=new ArrayList<>();
    while(!q.isEmpty()){
        TreeNode cur=q.poll();
        res.add(cur.val);
        if(cur.left!=null){
            q.add(cur.left);
        }
        if(cur.right!=null){
            q.add(cur.right);
        }
 
    }
    int[] resArray=new int[res.size()];
    for(int i=0;i<res.size();i++){
        resArray[i]=res.get(i);
    }
    return resArray;
}

public TreeNode MirrorTree(TreeNode root){
    if(root==null) return null;
    Stack<TreeNode> stack =new Stack<>();
    stack.add(root);
    while(!stack.isEmpty()){
        TreeNode root =stack.pop();
        TreeNode temp=root.left;
        root.left=root.right;
        root.right=temp;
        if(root.left!=null){
            stack.push(root.left);
        }
        if(root.right!=null){
            stack.push(root.right);
        }
    }
    return root;
}

public TreeNode MirrorTree(TreeNode root){
    if(root==null) return null;
    TreeNode r=MirrorTree(root.left);
    TreeNode l=MirrorTree(root.right);
    root.left=l;
    root.right=r;
    return root;
}

public ListNode reverse(ListNode head){
    ListNode prev=null;
    ListNode next= head.next;
    while (next!=null){
        head.next=prev;
        prev=head;
        head=next;
        next=next.next;
    }
    head.next=prev;
    prev=head;
    return prev;
}

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
            return head;
    }
    ListNode newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

public ListNode reverseList(ListNode head) {       
    ListNode kong=new ListNode(); 
    ListNode temp; 
    while (head!=null){ 
        temp=head.next;
        head.next=kong.next; 
        kong.next=head; head=temp; 
    } 
    return kong.next; 
}

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder,0,postorder.length-1);
    }
    public boolean recur(int[] postorder,int i,int j){
        if(i>=j) return true;

        int p=i;
        while(postorder[p]<postorder[j]) p++;
        int m=p;
        while(postorder[p]>postorder[j]) p++;
        return p==j && recur(postorder,i,m-1) && recur(postorder,m,j-1);
    }
}