taixingbi/*dfs.java

## *dfs.java
Depth
1 maximun depth: 104

104. Maximum Depth of Binary Tree
https://leetcode.com/problems/maximum-depth-of-binary-tree/description/

class Solution {
    public int maxDepth(TreeNode root) {
        //O(N)
        if(root==null) return 0;
        return 1+ Math.max( maxDepth(root.left), maxDepth(root.right) );
    }
}

        559. Maximum Depth of N-ary Tree
        https://leetcode.com/problems/maximum-depth-of-n-ary-tree/description/
        class Solution(object):
            def maxDepth(self, root):
                """
                :type root: Node
                :rtype: int
                """
                if root:
                    Max= 1
                    for child in root.children:
                        Max= max(Max, 1+self.maxDepth(child) )
                    return Max
                return 0

110. Balanced Binary Tree
https://leetcode.com/problems/balanced-binary-tree/description/
class Solution {
    private int depth(TreeNode root){
        if(root==null) return 0;
        return 1 + Math.max( depth(root.left), depth(root.right) );
    }

    //O(N)
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;

        int left= depth(root.left);
        int right= depth(root.right);

        return Math.abs(left-right) <=1 && isBalanced(root.left) && isBalanced(root.right) ;
    }


#-------------------------------------------------------------------------------------------
111. Minimum Depth of Binary Tree
https://leetcode.com/problems/minimum-depth-of-binary-tree/description/
class Solution {
    public int minDepth(TreeNode root) {
        //O(N)
        if(root==null) return 0;
        if(root.left==null && root.right==null) return 1;
        int minDepth= Integer.MAX_VALUE;
        if(root.left != null)  minDepth= Math.min(minDepth, minDepth(root.left) );
        if(root.right != null)  minDepth= Math.min(minDepth, minDepth(root.right) );
        return minDepth+1;
    }
}

        222. Count Complete Tree Nodes
        https://leetcode.com/problems/count-complete-tree-nodes/description/
                Input:
            1
           / \
          2   3
         / \  /
        4  5 6

        Output: 6
        class Solution(object):
            def countNodes(self, root):
                """
                :type root: TreeNode
                :rtype: int
                """
                if not root:    return 0

                def getDepth(root):
                    if root:    return 1 + getDepth(root.left)
                    return 0

                leftDepth = getDepth(root.left)
                rightDepth = getDepth(root.right)

                if leftDepth == rightDepth: return 2**leftDepth + self.countNodes(root.right)
                else:   return 2**rightDepth + self.countNodes(root.left)

## bst.java
700. Search in a Binary Search Tree
https://leetcode.com/problems/search-in-a-binary-search-tree/description/
Given the tree:
        4
       / \
      2   7
     / \
    1   3

And the value to search: 2
You should return this subtree:

      2
     / \
    1   3
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while(root!=null){
            if(root.val==val) return root;
            root= val > root.val ? root.right : root.left;
        }
        return null;
    }
}

701. Insert into a Binary Search Tree
https://leetcode.com/problems/insert-into-a-binary-search-tree/submissions/
Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.
Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.
For example,
Given the tree:
        4
       / \
      2   7
     / \
    1   3
And the value to insert: 5
You can return this binary search tree:

         4
       /   \
      2     7
     / \   /
    1   3 5

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null) return new TreeNode(val);

        TreeNode node= root;
        while(true){
            if(val >= node.val){
                if(node.right==null){
                    node.right= new TreeNode(val);
                    break;
                } else node= node.right;
            }

        if(val < node.val){
                if(node.left==null){
                    node.left= new TreeNode(val);
                    break;
                } else node= node.left;
            }
        }

        return root;
    }
}

## build bst.java
Array to Binary search tree: 108 / 109

108. Convert Sorted Array to BST
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
      0
     / \
   -3   9
   /   /
 -10  5
class Solution {

    public TreeNode dfs(int[] nums, int l, int r){
        if(l>r) return null;

        int m= (l+r)/2;
        TreeNode node= new TreeNode( nums[m] );
        node.left= dfs(nums, l, m-1);
        node.right= dfs(nums, m+1, r);

        return node;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length-1);
    }
}

109. Convert Sorted List to Binary Search Tree
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/
class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        #runtime complexity: O(n*2) space complexity: O(log(n)) n=len(nodes)
        nums= []
        while head:
            nums.append(head.val)
            head= head.next

#-------------------------------------------------------------------------
Traversa to BST

105. Construct Binary Tree from Preorder and Inorder Traversa
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
    3
   / \
  9  20
    /  \
   15   7

class Solution {
  // start from first preorder element
  int pre_idx = 0;
  int[] preorder;
  int[] inorder;
  HashMap<Integer, Integer> idx_map = new HashMap<Integer, Integer>();

  public TreeNode helper(int in_left, int in_right) {
    // if there is no elements to construct subtrees
    if (in_left == in_right)
      return null;

    // pick up pre_idx element as a root
    int root_val = preorder[pre_idx];
    TreeNode root = new TreeNode(root_val);

    // root splits inorder list
    // into left and right subtrees
    int index = idx_map.get(root_val);

    // recursion
    pre_idx++;
    // build left subtree
    root.left = helper(in_left, index);
    // build right subtree
    root.right = helper(index + 1, in_right);
    return root;
  }

  public TreeNode buildTree(int[] preorder, int[] inorder) {
    this.preorder = preorder;
    this.inorder = inorder;

    // build a hashmap value -> its index
    int idx = 0;
    for (Integer val : inorder)
      idx_map.put(val, idx++);
    return helper(0, inorder.length);
  }
}

106. Construct Binary Tree from Inorder and Postorder Traversal
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

        def dfs(inorder):
            if inorder:
                root= TreeNode(postorder.pop())
                idx= inorder.index(root.val)
                root.right= dfs(inorder[idx+1:])
                root.left= dfs(inorder[:idx])
                return root

297. Serialize and Deserialize Binary Tree
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization
algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized
to the original tree structure.
Example:
You may serialize the following tree:
    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]"
Clarification: The above format is the same as how LeetCode serializes a binary tree.
You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
public class Codec {
    private static final String spliter = ",";
    private static final String NN = "X";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        buildString(root, sb);
        return sb.toString();
    }

    private void buildString(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(NN).append(spliter);
        } else {
            sb.append(node.val).append(spliter);
            buildString(node.left, sb);
            buildString(node.right,sb);
        }
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Deque<String> nodes = new LinkedList<>();
        nodes.addAll(Arrays.asList(data.split(spliter)));
        return buildTree(nodes);
    }

    private TreeNode buildTree(Deque<String> nodes) {
        String val = nodes.remove();
        if (val.equals(NN)) return null;
        else {
            TreeNode node = new TreeNode(Integer.valueOf(val));
            node.left = buildTree(nodes);
            node.right = buildTree(nodes);
            return node;
        }
    }
}


## islands.java
200. Number of Islands
https://leetcode.com/problems/number-of-islands/submissions/
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is
formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011

Output: 3
class Solution {
   public void printboard(int[][] board) {
		for(int[] list: board) {
			System.out.println( Arrays.toString(list) );
		}
	}

	int m, n;
	int[][] dir= {{0, 1}, {0, -1},{1, 0},{-1, 0} };
	void dfs(int[][] grid, int i, int j) {
		if( i<0 || i>=m || j<0 || j>=n || grid[i][j]==0)  return;
		grid[i][j]= 0;

		for(int[] d: dir) {
			int x= d[0]+i, y= d[1]+j;
			dfs(grid, x, y);
		}
	}

	public  int NumberofIslands__( int[][] grid) {
		printboard(grid);

		int cnt= 0;
		m= grid.length;
		n= grid[0].length;

		for(int i=0; i<m; i++) {
			for(int j=0; j<n; j++) {
				if(grid[i][j]==1) {
					dfs(grid, i, j);
					cnt++;
				}
			}
		}
		return cnt;
	}
}

694. Number of Distinct Islands
https://leetcode.com/problems/number-of-distinct-islands/solution/
Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.)
You may assume all four edges of the grid are surrounded by water.
Count the number of distinct islands. An island is considered to be the same as another
if and only if one island can be translated (and not rotated or reflected) to equal the other.
Example 1:
11000
11000
00011
00011
Given the above grid map, return 1.
Example 2:
11011
10000
00001
11011
class Solution {
    void dfs(int[][] grid, Set<Integer> shape, int i, int j, int i0, int j0) {
        if( 0<=i && i< grid.length && 0<=j && j< grid[0].length && grid[i][j]==1  ) {
            grid[i][j]= 0;
            shape.add( (i-i0)*2*grid[0].length + (j-j0) );//grid[0].length because our local row-coordinate could be negative.
            dfs( grid, shape, i+1, j, i0, j0);
            dfs( grid, shape, i-1, j, i0, j0);
            dfs( grid, shape, i, j+1, i0, j0);
            dfs( grid, shape, i, j-1, i0, j0);
        }
	}
    public int numDistinctIslands(int[][] grid) {
        if(grid==null || grid.length==0) return 0;
        int cnt= 0;

        Set shapes= new HashSet<HashSet<Integer>>();

    	for(int i=0; i<grid.length; i++) {
    		for(int j=0; j<grid[0].length; j++) {
    			Set<Integer> shape= new HashSet<>();
    			if( grid[i][j]==1 ) {
    				dfs(grid, shape, i, j, i, j);
    				cnt++;
    			}
    			if(!shape.isEmpty())  shapes.add(shape);
    		}
    	}
    	return shapes.size();
    }
}

## level.java
depth: 102/ 637

102. Binary Tree Level Order Traversal
https://leetcode.com/problems/binary-tree-level-order-traversal/description/
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]
# runtime complexity: O(n) n= number of nodes  space complexity: O(m) n + m m= maximun depth of tree to save call stack
#--------------------dfs----------------------
def dfs(root, dep):
    if root:
        d[dep].append(root.val)
        dfs(root.left, dep+1)
        dfs(root.right, dep+1)

d= collections.defaultdict(list)
dfs(root, 1)
return d.values()

        429. N-ary Tree Level Order Traversal
        https://leetcode.com/problems/n-ary-tree-level-order-traversal/description/
        class Solution(object):
            def levelOrder(self, root):
                """
                :type root: Node
                :rtype: List[List[int]]
                """
                # runtime complexity: O(n) n= number of nodes  space complexity: O(m) n + m m= maximun depth of tree to save call stack
                def dfs(root, dep):
                    if root:
                        d[dep].append(root.val)
                        for child in root.children:
                            dfs(child, dep+1)

                d= collections.defaultdict(list)
                dfs(root, 1)
                return d.values()


107. Binary Tree Level Order Traversal II
https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description/
    3
   / \
  9  20
    /  \
   15   7
return its bottom-up level order traversal as:
[
  [15,7],
  [9,20],
  [3]
]
class Solution(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        # runtime complexity: O(n) n= number of nodes  space complexity: O(m) n + m m= maximun depth of tree to save call stack
        #--------------------dfs----------------------
        def dfs(root, dep):
            if root:
                d[dep].append(root.val)
                dfs(root.left, dep+1)
                dfs(root.right, dep+1)

        d= collections.defaultdict(list)
        dfs(root, 1)
        ans= d.values()
        ans.reverse()
        return ans


103. Binary Tree Zigzag Level Order Traversal
https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/
   3
   / \
  9  20
    /  \
   15   7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]
class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        def dfs(root, dep):
            if root:
                d[dep].append(root.val)
                dfs(root.left, dep+1)
                dfs(root.right, dep+1)

        d= collections.defaultdict(list)
        dfs(root, 1)

        ans= []
        for key, vals in d.items():
            if key%2==0: vals.reverse()
            ans.append(vals)

        return ans

637. Average of Levels in Binary Tree
https://leetcode.com/problems/average-of-levels-in-binary-tree/description/
class Solution(object):
    def averageOfLevels(self, root):
        """
        :type root: TreeNode
        :rtype: List[float]
        """
        # runtime complexity: O(n) n= number of nodes  space complexity: O(m) n + m m= maximun depth of tree to save call stack
        #---------------------dfs----------------------------------------------------
        def dfs(root, dep):
            if root:
                d[dep].append(root.val)
                dfs(root.left, dep+1)
                dfs(root.right, dep+1)

        d= collections.defaultdict(list)
        dfs(root, 1)

        return [ 1.0*sum(nums)/len(nums) for nums in d.values()]

515. Find Largest Value in Each Tree Row
https://leetcode.com/problems/find-largest-value-in-each-tree-row/description/
Input:
          1
         / \
        3   2
       / \   \
      5   3   9
Output: [1, 3, 9]
class Solution(object):
    def largestValues(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        def dfs(root, dep):
            if root:
                d[dep].append(root.val)
                dfs(root.left, dep+1)
                dfs(root.right, dep+1)

        d= collections.defaultdict(list)
        dfs(root, 1)
        return [ max(nums) for nums in d.values() ]

## other.java
139. Word Break
https://leetcode.com/problems/word-break/description/

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """

        #---------------------dfs------------------------------
        #runtime complexity: O(n**2) n= size of recursion
        def dfs(st):
            if s[st:]:
                for word in wordDict:
                    if s[st:].find(word)==0:
                        end= st+len(word)
                        if end not in used:
                            used.append(end)
                            dfs(end)
            else: self.ans= True

        self.ans= False
        used= []
        dfs(0)
        return self.ans

## path sum.java
root->leaf:  112 / 113
                     / 129
not root->leaf:  437 / 124


112. Path Sum
https://leetcode.com/problems/path-sum/description/
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        # runtime complaxity O(N) space complexity O(hight)
        def dfs(root, sum):
            if root:
                if not root.left and not root.right and sum==root.val:  self.ans= True;return
                dfs(root.left, sum-root.val)
                dfs(root.right, sum-root.val)
                return

        self.ans= False #  if root == null, return False
        dfs(root, sum)
        return self.ans

113. Path Sum II
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1
Return:
[
   [5,4,11,2],
   [5,8,4,5]
]

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        #-------------------------------dfs-----------------------------------------------------------
        # runtime complaxity O(N) space complexity O(hight)
        def dfs(root, sum, path):
            if root:
                if not root.left and not root.right and sum==root.val:
                    ans.append(path+[root.val]);return
                dfs(root.left, sum-root.val, path+[root.val])
                dfs(root.right, sum-root.val, path+[root.val])
                return
        ans= []
        dfs(root, sum, [])
        return ans
        #---------------------------------bfs---------------------------------------
        # runtime complaxity O(N) N= len(nodes)   space complexity O(2**(hight-1)
        if not root: return []
        ans= []
        nodes= [(root, Sum, [])]
        while nodes:
            nextNodes= []
            for node, Sum, path in nodes:
                if not node.left and not node.right and Sum==node.val:  ans.append(path+[node.val])

                if node.left: nextNodes.append( (node.left, Sum-node.val, path+[node.val]) )
                if node.right: nextNodes.append( (node.right, Sum-node.val, path+[node.val]) )
            nodes= nextNodes

        return ans
129. Sum Root to Leaf Numbers
https://leetcode.com/problems/sum-root-to-leaf-numbers/description/

#---------------------------------------------------------------------------------------
437. Path Sum III
https://leetcode.com/problems/path-sum-iii/description/
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1
Return 3. The paths that sum to 8 are:
1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11
class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
       # runtime complaxity O(N) space complexity O(hight)
        def dfs(root, sum):
            if not root:    return 0

            left, right= dfs(root.left, sum-root.val) , dfs(root.right, sum-root.val)
            if root.val==sum:   cnt= 1
            else: cnt=0
            return cnt+left+right

        if not root: return 0
        return dfs(root, sum) + self.pathSum(root.left, sum)+ self.pathSum(root.right, sum)

 124. Binary Tree Maximum Path Sum
 https://leetcode.com/problems/binary-tree-maximum-path-sum/description/
 class Solution(object):
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def dfs(root):
            if not root:    return 0

            left,right = dfs(root.left), dfs(root.right)
            left = left if left > 0 else 0
            right = right if right > 0 else 0

            self.maxSum = max(self.maxSum, root.val+left+right)
            return max(left, right) + root.val

        self.maxSum = float('-inf')
        dfs(root)
        return self.maxSum

687. Longest Univalue Path
https://leetcode.com/problems/longest-univalue-path/description/
Input:

              1
             / \
            4   5
           / \   \
          4   4   5
Output:2

class Solution(object):
    def longestUnivaluePath(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def dfs(root):
            if not root:    return 0

            left, right= dfs(root.left), dfs(root.right)

            if root.left and root.left.val==root.val: left+= 1
            else: left=0
            if root.right and root.right.val==root.val: right+= 1
            else: right=0

            self.ans= max(self.ans, left+right)
            return max(left, right)

        self.ans= 0
        dfs(root)
        return self.ans


257. Binary Tree Paths
https://leetcode.com/problems/binary-tree-paths/description/
Input:

   1
 /   \
2     3
 \
  5

Output: ["1->2->5", "1->3"]

class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        # runtime complaxity O(n) space complexity O(hight*2)  n= number of nodes  height= call stack
        def dfs(root, path):
            if root:
                path= path + '->' + str(root.val) if path else str(root.val)
                if not root.left and not root.right:   ans.append(path)
                dfs(root.left, path)
                dfs(root.right, path)

        ans = []
        dfs(root, "")
        return ans


## Traversal.java
inorder: 94
preorder: 144 / 429
postorder: 145 / 590

94. Binary Tree Inorder Traversal
https://leetcode.com/problems/binary-tree-inorder-traversal/description/
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        #------------------dfs-------------------------------------
        #runtime complexity: O(n)  space complexity: O(1)
        def dfs(root):
            if root:
                dfs(root.left)
                ans.append(root.val)
                dfs(root.right)

        ans= []
        dfs(root)
        return ans
        230. Kth Smallest Element in a BST
        https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/
        Input: root = [3,1,4,null,2], k = 1
           3
          / \
         1   4
          \
           2
        Output: 1
        class Solution(object):
            def kthSmallest(self, root, k):
                """
                :type root: TreeNode
                :type k: int
                :rtype: int
                """
                 def dfs(root):
                    if root:
                        dfs(root.left)
                        self.cnt += 1
                        if self.cnt==k:
                            self.ans= root.val
                            return
                        dfs(root.right)

                self.cnt= 0
                dfs(root)
                return self.ans
                /
                def dfs(root):
                    if root:
                        dfs(root.left)
                        self.l.append(root.val)
                        dfs(root.right)
                        return

                self.l= []
                dfs(root)
                return self.l[k-1]

        114. Flatten Binary Tree to Linked List
        https://leetcode.com/problems/flatten-binary-tree-to-linked-list/description/
            class Solution(object):
        def flatten(self, root):
            """
            :type root: TreeNode
            :rtype: void Do not return anything, modify root in-place instead.
            """

            def dfs(node):
                if not node: return
                # pre-order
                nums.append(node.val)
                if node.left: dfs(node.left)
                if node.right: dfs(node.right)

            nums= []
            dfs(root)

            while nums:
                val= nums.pop(0)
                root.val= val
                root.left= None

                if nums and not root.right: root.right= TreeNode(0) #add right node
                root= root.right

144. Binary Tree Preorder Traversal
https://leetcode.com/problems/binary-tree-preorder-traversal/description/
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        #------------------dfs-------------------------------------
        #runtime complexity: O(n)  space complexity: O(1)
        def dfs(root):
            if root:
                ans.append(root.val)
                dfs(root.left)
                dfs(root.right)

        ans= []
        dfs(root)
        return ans

    589. N-ary Tree Preorder Traversal
    https://leetcode.com/problems/n-ary-tree-preorder-traversal/description/
    class Solution(object):
        def preorder(self, root):
            """
            :type root: Node
            :rtype: List[int]
            """
            #runtime complexity: O(n)  space complexity: O(1)
            def dfs(root):
                if root:
                    ans.append(root.val)
                    for child in root.children:
                        dfs(child)

            ans= []
            dfs(root)
            return ans


145. Binary Tree Postorder Traversal
https://leetcode.com/problems/binary-tree-postorder-traversal/description/
class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        #runtime complexity: O(n)  space complexity: O(1)
        def dfs(root):
            if root:
                dfs(root.left)
                dfs(root.right)
                ans.append(root.val)

        ans= []
        dfs(root)
        return ans

        590. N-ary Tree Postorder Traversal
        https://leetcode.com/problems/n-ary-tree-postorder-traversal/description/
        class Solution(object):
        def postorder(self, root):
            """
            :type root: Node
            :rtype: List[int]
            """
            #runtime complexity: O(n)  space complexity: O(1)
            def dfs(root):
                if root:
                    for child in root.children:
                        dfs(child)
                    ans.append(root.val)

            ans= []
            dfs(root)
                return ans
	Depth
	1 maximun depth: 104

	104. Maximum Depth of Binary Tree
	https://leetcode.com/problems/maximum-depth-of-binary-tree/description/

	class Solution {
	public int maxDepth(TreeNode root) {
	//O(N)
	if(root==null) return 0;
	return 1+ Math.max( maxDepth(root.left), maxDepth(root.right) );
	}
	}

	559. Maximum Depth of N-ary Tree
	https://leetcode.com/problems/maximum-depth-of-n-ary-tree/description/
	class Solution(object):
	def maxDepth(self, root):
	"""
	:type root: Node
	:rtype: int
	"""
	if root:
	Max= 1
	for child in root.children:
	Max= max(Max, 1+self.maxDepth(child) )
	return Max
	return 0

	110. Balanced Binary Tree
	https://leetcode.com/problems/balanced-binary-tree/description/
	class Solution {
	private int depth(TreeNode root){
	if(root==null) return 0;
	return 1 + Math.max( depth(root.left), depth(root.right) );
	}

	//O(N)
	public boolean isBalanced(TreeNode root) {
	if(root==null) return true;

	int left= depth(root.left);
	int right= depth(root.right);

	return Math.abs(left-right) <=1 && isBalanced(root.left) && isBalanced(root.right) ;
	}


	#-------------------------------------------------------------------------------------------
	111. Minimum Depth of Binary Tree
	https://leetcode.com/problems/minimum-depth-of-binary-tree/description/
	class Solution {
	public int minDepth(TreeNode root) {
	//O(N)
	if(root==null) return 0;
	if(root.left==null && root.right==null) return 1;
	int minDepth= Integer.MAX_VALUE;
	if(root.left != null) minDepth= Math.min(minDepth, minDepth(root.left) );
	if(root.right != null) minDepth= Math.min(minDepth, minDepth(root.right) );
	return minDepth+1;
	}
	}

	222. Count Complete Tree Nodes
	https://leetcode.com/problems/count-complete-tree-nodes/description/
	Input:
	1
	/ \
	2 3
	/ \ /
	4 5 6

	Output: 6
	class Solution(object):
	def countNodes(self, root):
	"""
	:type root: TreeNode
	:rtype: int
	"""
	if not root: return 0

	def getDepth(root):
	if root: return 1 + getDepth(root.left)
	return 0

	leftDepth = getDepth(root.left)
	rightDepth = getDepth(root.right)

	if leftDepth == rightDepth: return 2**leftDepth + self.countNodes(root.right)
	else: return 2**rightDepth + self.countNodes(root.left)
	700. Search in a Binary Search Tree
	https://leetcode.com/problems/search-in-a-binary-search-tree/description/
	Given the tree:
	4
	/ \
	2 7
	/ \
	1 3

	And the value to search: 2
	You should return this subtree:

	2
	/ \
	1 3
	class Solution {
	public TreeNode searchBST(TreeNode root, int val) {
	while(root!=null){
	if(root.val==val) return root;
	root= val > root.val ? root.right : root.left;
	}
	return null;
	}
	}

	701. Insert into a Binary Search Tree
	https://leetcode.com/problems/insert-into-a-binary-search-tree/submissions/
	Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.
	Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.
	For example,
	Given the tree:
	4
	/ \
	2 7
	/ \
	1 3
	And the value to insert: 5
	You can return this binary search tree:

	4
	/ \
	2 7
	/ \ /
	1 3 5

	# Definition for a binary tree node.
	# class TreeNode(object):
	# def __init__(self, x):
	# self.val = x
	# self.left = None
	# self.right = None

	class Solution {
	public TreeNode insertIntoBST(TreeNode root, int val) {
	if(root==null) return new TreeNode(val);

	TreeNode node= root;
	while(true){
	if(val >= node.val){
	if(node.right==null){
	node.right= new TreeNode(val);
	break;
	} else node= node.right;
	}

	if(val < node.val){
	if(node.left==null){
	node.left= new TreeNode(val);
	break;
	} else node= node.left;
	}
	}

	return root;
	}
	}
	Array to Binary search tree: 108 / 109

	108. Convert Sorted Array to BST
	https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/
	Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
	For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
	Example:
	Given the sorted array: [-10,-3,0,5,9],
	One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
	0
	/ \
	-3 9
	/ /
	-10 5
	class Solution {

	public TreeNode dfs(int[] nums, int l, int r){
	if(l>r) return null;

	int m= (l+r)/2;
	TreeNode node= new TreeNode( nums[m] );
	node.left= dfs(nums, l, m-1);
	node.right= dfs(nums, m+1, r);

	return node;
	}

	public TreeNode sortedArrayToBST(int[] nums) {
	return dfs(nums, 0, nums.length-1);
	}
	}

	109. Convert Sorted List to Binary Search Tree
	https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/
	class Solution(object):
	def sortedListToBST(self, head):
	"""
	:type head: ListNode
	:rtype: TreeNode
	"""
	#runtime complexity: O(n*2) space complexity: O(log(n)) n=len(nodes)
	nums= []
	while head:
	nums.append(head.val)
	head= head.next

	#-------------------------------------------------------------------------
	Traversa to BST

	105. Construct Binary Tree from Preorder and Inorder Traversa
	https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
	Given preorder and inorder traversal of a tree, construct the binary tree.
	Note:
	You may assume that duplicates do not exist in the tree.
	For example, given
	preorder = [3,9,20,15,7]
	inorder = [9,3,15,20,7]
	Return the following binary tree:
	3
	/ \
	9 20
	/ \
	15 7

	class Solution {
	// start from first preorder element
	int pre_idx = 0;
	int[] preorder;
	int[] inorder;
	HashMap<Integer, Integer> idx_map = new HashMap<Integer, Integer>();

	public TreeNode helper(int in_left, int in_right) {
	// if there is no elements to construct subtrees
	if (in_left == in_right)
	return null;

	// pick up pre_idx element as a root
	int root_val = preorder[pre_idx];
	TreeNode root = new TreeNode(root_val);

	// root splits inorder list
	// into left and right subtrees
	int index = idx_map.get(root_val);

	// recursion
	pre_idx++;
	// build left subtree
	root.left = helper(in_left, index);
	// build right subtree
	root.right = helper(index + 1, in_right);
	return root;
	}

	public TreeNode buildTree(int[] preorder, int[] inorder) {
	this.preorder = preorder;
	this.inorder = inorder;

	// build a hashmap value -> its index
	int idx = 0;
	for (Integer val : inorder)
	idx_map.put(val, idx++);
	return helper(0, inorder.length);
	}
	}

	106. Construct Binary Tree from Inorder and Postorder Traversal
	inorder = [9,3,15,20,7]
	postorder = [9,15,7,20,3]
	Return the following binary tree:

	3
	/ \
	9 20
	/ \
	15 7

	def dfs(inorder):
	if inorder:
	root= TreeNode(postorder.pop())
	idx= inorder.index(root.val)
	root.right= dfs(inorder[idx+1:])
	root.left= dfs(inorder[:idx])
	return root

	297. Serialize and Deserialize Binary Tree
	https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
	Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization
	algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized
	to the original tree structure.
	Example:
	You may serialize the following tree:
	1
	/ \
	2 3
	/ \
	4 5

	as "[1,2,3,null,null,4,5]"
	Clarification: The above format is the same as how LeetCode serializes a binary tree.
	You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
	public class Codec {
	private static final String spliter = ",";
	private static final String NN = "X";

	// Encodes a tree to a single string.
	public String serialize(TreeNode root) {
	StringBuilder sb = new StringBuilder();
	buildString(root, sb);
	return sb.toString();
	}

	private void buildString(TreeNode node, StringBuilder sb) {
	if (node == null) {
	sb.append(NN).append(spliter);
	} else {
	sb.append(node.val).append(spliter);
	buildString(node.left, sb);
	buildString(node.right,sb);
	}
	}
	// Decodes your encoded data to tree.
	public TreeNode deserialize(String data) {
	Deque<String> nodes = new LinkedList<>();
	nodes.addAll(Arrays.asList(data.split(spliter)));
	return buildTree(nodes);
	}

	private TreeNode buildTree(Deque<String> nodes) {
	String val = nodes.remove();
	if (val.equals(NN)) return null;
	else {
	TreeNode node = new TreeNode(Integer.valueOf(val));
	node.left = buildTree(nodes);
	node.right = buildTree(nodes);
	return node;
	}
	}
	}
	200. Number of Islands
	https://leetcode.com/problems/number-of-islands/submissions/
	Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is
	formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
	Example 1:
	Input:
	11110
	11010
	11000
	00000
	Output: 1
	Example 2:
	Input:
	11000
	11000
	00100
	00011

	Output: 3
	class Solution {
	public void printboard(int[][] board) {
	for(int[] list: board) {
	System.out.println( Arrays.toString(list) );
	}
	}

	int m, n;
	int[][] dir= {{0, 1}, {0, -1},{1, 0},{-1, 0} };
	void dfs(int[][] grid, int i, int j) {
	if( i<0 \|\| i>=m \|\| j<0 \|\| j>=n \|\| grid[i][j]==0) return;
	grid[i][j]= 0;

	for(int[] d: dir) {
	int x= d[0]+i, y= d[1]+j;
	dfs(grid, x, y);
	}
	}

	public int NumberofIslands__( int[][] grid) {
	printboard(grid);

	int cnt= 0;
	m= grid.length;
	n= grid[0].length;

	for(int i=0; i<m; i++) {
	for(int j=0; j<n; j++) {
	if(grid[i][j]==1) {
	dfs(grid, i, j);
	cnt++;
	}
	}
	}
	return cnt;
	}
	}

	694. Number of Distinct Islands
	https://leetcode.com/problems/number-of-distinct-islands/solution/
	Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.)
	You may assume all four edges of the grid are surrounded by water.
	Count the number of distinct islands. An island is considered to be the same as another
	if and only if one island can be translated (and not rotated or reflected) to equal the other.
	Example 1:
	11000
	11000
	00011
	00011
	Given the above grid map, return 1.
	Example 2:
	11011
	10000
	00001
	11011
	class Solution {
	void dfs(int[][] grid, Set<Integer> shape, int i, int j, int i0, int j0) {
	if( 0<=i && i< grid.length && 0<=j && j< grid[0].length && grid[i][j]==1 ) {
	grid[i][j]= 0;
	shape.add( (i-i0)2grid[0].length + (j-j0) );//grid[0].length because our local row-coordinate could be negative.
	dfs( grid, shape, i+1, j, i0, j0);
	dfs( grid, shape, i-1, j, i0, j0);
	dfs( grid, shape, i, j+1, i0, j0);
	dfs( grid, shape, i, j-1, i0, j0);
	}
	}
	public int numDistinctIslands(int[][] grid) {
	if(grid==null \|\| grid.length==0) return 0;
	int cnt= 0;

	Set shapes= new HashSet<HashSet<Integer>>();

	for(int i=0; i<grid.length; i++) {
	for(int j=0; j<grid[0].length; j++) {
	Set<Integer> shape= new HashSet<>();
	if( grid[i][j]==1 ) {
	dfs(grid, shape, i, j, i, j);
	cnt++;
	}
	if(!shape.isEmpty()) shapes.add(shape);
	}
	}
	return shapes.size();
	}
	}
	depth: 102/ 637

	102. Binary Tree Level Order Traversal
	https://leetcode.com/problems/binary-tree-level-order-traversal/description/
	3
	/ \
	9 20
	/ \
	15 7
	return its level order traversal as:
	[
	[3],
	[9,20],
	[15,7]
	]
	# runtime complexity: O(n) n= number of nodes space complexity: O(m) n + m m= maximun depth of tree to save call stack
	#--------------------dfs----------------------
	def dfs(root, dep):
	if root:
	d[dep].append(root.val)
	dfs(root.left, dep+1)
	dfs(root.right, dep+1)

	d= collections.defaultdict(list)
	dfs(root, 1)
	return d.values()

	429. N-ary Tree Level Order Traversal
	https://leetcode.com/problems/n-ary-tree-level-order-traversal/description/
	class Solution(object):
	def levelOrder(self, root):
	"""
	:type root: Node
	:rtype: List[List[int]]
	"""
	# runtime complexity: O(n) n= number of nodes space complexity: O(m) n + m m= maximun depth of tree to save call stack
	def dfs(root, dep):
	if root:
	d[dep].append(root.val)
	for child in root.children:
	dfs(child, dep+1)

	d= collections.defaultdict(list)
	dfs(root, 1)
	return d.values()



	107. Binary Tree Level Order Traversal II
	https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description/
	3
	/ \
	9 20
	/ \
	15 7
	return its bottom-up level order traversal as:
	[
	[15,7],
	[9,20],
	[3]
	]
	class Solution(object):
	def levelOrderBottom(self, root):
	"""
	:type root: TreeNode
	:rtype: List[List[int]]
	"""
	# runtime complexity: O(n) n= number of nodes space complexity: O(m) n + m m= maximun depth of tree to save call stack
	#--------------------dfs----------------------
	def dfs(root, dep):
	if root:
	d[dep].append(root.val)
	dfs(root.left, dep+1)
	dfs(root.right, dep+1)

	d= collections.defaultdict(list)
	dfs(root, 1)
	ans= d.values()
	ans.reverse()
	return ans


	103. Binary Tree Zigzag Level Order Traversal
	https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/
	3
	/ \
	9 20
	/ \
	15 7
	return its zigzag level order traversal as:
	[
	[3],
	[20,9],
	[15,7]
	]
	class Solution(object):
	def zigzagLevelOrder(self, root):
	"""
	:type root: TreeNode
	:rtype: List[List[int]]
	"""
	def dfs(root, dep):
	if root:
	d[dep].append(root.val)
	dfs(root.left, dep+1)
	dfs(root.right, dep+1)

	d= collections.defaultdict(list)
	dfs(root, 1)

	ans= []
	for key, vals in d.items():
	if key%2==0: vals.reverse()
	ans.append(vals)

	return ans

	637. Average of Levels in Binary Tree
	https://leetcode.com/problems/average-of-levels-in-binary-tree/description/
	class Solution(object):
	def averageOfLevels(self, root):
	"""
	:type root: TreeNode
	:rtype: List[float]
	"""
	# runtime complexity: O(n) n= number of nodes space complexity: O(m) n + m m= maximun depth of tree to save call stack
	#---------------------dfs----------------------------------------------------
	def dfs(root, dep):
	if root:
	d[dep].append(root.val)
	dfs(root.left, dep+1)
	dfs(root.right, dep+1)

	d= collections.defaultdict(list)
	dfs(root, 1)

	return [ 1.0*sum(nums)/len(nums) for nums in d.values()]

	515. Find Largest Value in Each Tree Row
	https://leetcode.com/problems/find-largest-value-in-each-tree-row/description/
	Input:
	1
	/ \
	3 2
	/ \ \
	5 3 9
	Output: [1, 3, 9]
	class Solution(object):
	def largestValues(self, root):
	"""
	:type root: TreeNode
	:rtype: List[int]
	"""
	def dfs(root, dep):
	if root:
	d[dep].append(root.val)
	dfs(root.left, dep+1)
	dfs(root.right, dep+1)

	d= collections.defaultdict(list)
	dfs(root, 1)
	return [ max(nums) for nums in d.values() ]
	139. Word Break
	https://leetcode.com/problems/word-break/description/

	class Solution(object):
	def wordBreak(self, s, wordDict):
	"""
	:type s: str
	:type wordDict: List[str]
	:rtype: bool
	"""

	#---------------------dfs------------------------------
	#runtime complexity: O(n**2) n= size of recursion
	def dfs(st):
	if s[st:]:
	for word in wordDict:
	if s[st:].find(word)==0:
	end= st+len(word)
	if end not in used:
	used.append(end)
	dfs(end)
	else: self.ans= True

	self.ans= False
	used= []
	dfs(0)
	return self.ans
	root->leaf: 112 / 113
	/ 129
	not root->leaf: 437 / 124


	112. Path Sum
	https://leetcode.com/problems/path-sum/description/
	Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
	Note: A leaf is a node with no children.
	Example:
	Given the below binary tree and sum = 22,
	5
	/ \
	4 8
	/ / \
	11 13 4
	/ \ \
	7 2 1
	return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

	class Solution(object):
	def hasPathSum(self, root, sum):
	"""
	:type root: TreeNode
	:type sum: int
	:rtype: bool
	"""
	# runtime complaxity O(N) space complexity O(hight)
	def dfs(root, sum):
	if root:
	if not root.left and not root.right and sum==root.val: self.ans= True;return
	dfs(root.left, sum-root.val)
	dfs(root.right, sum-root.val)
	return

	self.ans= False # if root == null, return False
	dfs(root, sum)
	return self.ans

	113. Path Sum II
	5
	/ \
	4 8
	/ / \
	11 13 4
	/ \ / \
	7 2 5 1
	Return:
	[
	[5,4,11,2],
	[5,8,4,5]
	]

	class Solution(object):
	def pathSum(self, root, sum):
	"""
	:type root: TreeNode
	:type sum: int
	:rtype: List[List[int]]
	"""
	#-------------------------------dfs-----------------------------------------------------------
	# runtime complaxity O(N) space complexity O(hight)
	def dfs(root, sum, path):
	if root:
	if not root.left and not root.right and sum==root.val:
	ans.append(path+[root.val]);return
	dfs(root.left, sum-root.val, path+[root.val])
	dfs(root.right, sum-root.val, path+[root.val])
	return
	ans= []
	dfs(root, sum, [])
	return ans
	#---------------------------------bfs---------------------------------------
	# runtime complaxity O(N) N= len(nodes) space complexity O(2**(hight-1)
	if not root: return []
	ans= []
	nodes= [(root, Sum, [])]
	while nodes:
	nextNodes= []
	for node, Sum, path in nodes:
	if not node.left and not node.right and Sum==node.val: ans.append(path+[node.val])

	if node.left: nextNodes.append( (node.left, Sum-node.val, path+[node.val]) )
	if node.right: nextNodes.append( (node.right, Sum-node.val, path+[node.val]) )
	nodes= nextNodes

	return ans
	129. Sum Root to Leaf Numbers
	https://leetcode.com/problems/sum-root-to-leaf-numbers/description/

	#---------------------------------------------------------------------------------------
	437. Path Sum III
	https://leetcode.com/problems/path-sum-iii/description/
	root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
	10
	/ \
	5 -3
	/ \ \
	3 2 11
	/ \ \
	3 -2 1
	Return 3. The paths that sum to 8 are:
	1. 5 -> 3
	2. 5 -> 2 -> 1
	3. -3 -> 11
	class Solution(object):
	def pathSum(self, root, sum):
	"""
	:type root: TreeNode
	:type sum: int
	:rtype: int
	"""
	# runtime complaxity O(N) space complexity O(hight)
	def dfs(root, sum):
	if not root: return 0

	left, right= dfs(root.left, sum-root.val) , dfs(root.right, sum-root.val)
	if root.val==sum: cnt= 1
	else: cnt=0
	return cnt+left+right

	if not root: return 0
	return dfs(root, sum) + self.pathSum(root.left, sum)+ self.pathSum(root.right, sum)

	124. Binary Tree Maximum Path Sum
	https://leetcode.com/problems/binary-tree-maximum-path-sum/description/
	class Solution(object):
	def maxPathSum(self, root):
	"""
	:type root: TreeNode
	:rtype: int
	"""
	def dfs(root):
	if not root: return 0

	left,right = dfs(root.left), dfs(root.right)
	left = left if left > 0 else 0
	right = right if right > 0 else 0

	self.maxSum = max(self.maxSum, root.val+left+right)
	return max(left, right) + root.val

	self.maxSum = float('-inf')
	dfs(root)
	return self.maxSum

	687. Longest Univalue Path
	https://leetcode.com/problems/longest-univalue-path/description/
	Input:

	1
	/ \
	4 5
	/ \ \
	4 4 5
	Output:2

	class Solution(object):
	def longestUnivaluePath(self, root):
	"""
	:type root: TreeNode
	:rtype: int
	"""
	def dfs(root):
	if not root: return 0

	left, right= dfs(root.left), dfs(root.right)

	if root.left and root.left.val==root.val: left+= 1
	else: left=0
	if root.right and root.right.val==root.val: right+= 1
	else: right=0

	self.ans= max(self.ans, left+right)
	return max(left, right)

	self.ans= 0
	dfs(root)
	return self.ans


	257. Binary Tree Paths
	https://leetcode.com/problems/binary-tree-paths/description/
	Input:

	1
	/ \
	2 3
	\
	5

	Output: ["1->2->5", "1->3"]

	class Solution(object):
	def binaryTreePaths(self, root):
	"""
	:type root: TreeNode
	:rtype: List[str]
	"""
	# runtime complaxity O(n) space complexity O(hight*2) n= number of nodes height= call stack
	def dfs(root, path):
	if root:
	path= path + '->' + str(root.val) if path else str(root.val)
	if not root.left and not root.right: ans.append(path)
	dfs(root.left, path)
	dfs(root.right, path)

	ans = []
	dfs(root, "")
	return ans
	inorder: 94
	preorder: 144 / 429
	postorder: 145 / 590

	94. Binary Tree Inorder Traversal
	https://leetcode.com/problems/binary-tree-inorder-traversal/description/
	class Solution(object):
	def inorderTraversal(self, root):
	"""
	:type root: TreeNode
	:rtype: List[int]
	"""
	#------------------dfs-------------------------------------
	#runtime complexity: O(n) space complexity: O(1)
	def dfs(root):
	if root:
	dfs(root.left)
	ans.append(root.val)
	dfs(root.right)

	ans= []
	dfs(root)
	return ans
	230. Kth Smallest Element in a BST
	https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/
	Input: root = [3,1,4,null,2], k = 1
	3
	/ \
	1 4
	\
	2
	Output: 1
	class Solution(object):
	def kthSmallest(self, root, k):
	"""
	:type root: TreeNode
	:type k: int
	:rtype: int
	"""
	def dfs(root):
	if root:
	dfs(root.left)
	self.cnt += 1
	if self.cnt==k:
	self.ans= root.val
	return
	dfs(root.right)

	self.cnt= 0
	dfs(root)
	return self.ans
	/
	def dfs(root):
	if root:
	dfs(root.left)
	self.l.append(root.val)
	dfs(root.right)
	return

	self.l= []
	dfs(root)
	return self.l[k-1]

	114. Flatten Binary Tree to Linked List
	https://leetcode.com/problems/flatten-binary-tree-to-linked-list/description/
	class Solution(object):
	def flatten(self, root):
	"""
	:type root: TreeNode
	:rtype: void Do not return anything, modify root in-place instead.
	"""

	def dfs(node):
	if not node: return
	# pre-order
	nums.append(node.val)
	if node.left: dfs(node.left)
	if node.right: dfs(node.right)

	nums= []
	dfs(root)

	while nums:
	val= nums.pop(0)
	root.val= val
	root.left= None

	if nums and not root.right: root.right= TreeNode(0) #add right node
	root= root.right

	144. Binary Tree Preorder Traversal
	https://leetcode.com/problems/binary-tree-preorder-traversal/description/
	class Solution(object):
	def preorderTraversal(self, root):
	"""
	:type root: TreeNode
	:rtype: List[int]
	"""
	#------------------dfs-------------------------------------
	#runtime complexity: O(n) space complexity: O(1)
	def dfs(root):
	if root:
	ans.append(root.val)
	dfs(root.left)
	dfs(root.right)

	ans= []
	dfs(root)
	return ans

	589. N-ary Tree Preorder Traversal
	https://leetcode.com/problems/n-ary-tree-preorder-traversal/description/
	class Solution(object):
	def preorder(self, root):
	"""
	:type root: Node
	:rtype: List[int]
	"""
	#runtime complexity: O(n) space complexity: O(1)
	def dfs(root):
	if root:
	ans.append(root.val)
	for child in root.children:
	dfs(child)

	ans= []
	dfs(root)
	return ans



	145. Binary Tree Postorder Traversal
	https://leetcode.com/problems/binary-tree-postorder-traversal/description/
	class Solution(object):
	def postorderTraversal(self, root):
	"""
	:type root: TreeNode
	:rtype: List[int]
	"""
	#runtime complexity: O(n) space complexity: O(1)
	def dfs(root):
	if root:
	dfs(root.left)
	dfs(root.right)
	ans.append(root.val)

	ans= []
	dfs(root)
	return ans

	590. N-ary Tree Postorder Traversal
	https://leetcode.com/problems/n-ary-tree-postorder-traversal/description/
	class Solution(object):
	def postorder(self, root):
	"""
	:type root: Node
	:rtype: List[int]
	"""
	#runtime complexity: O(n) space complexity: O(1)
	def dfs(root):
	if root:
	for child in root.children:
	dfs(child)
	ans.append(root.val)

	ans= []
	dfs(root)
	return ans