Depth First Search (DFS) Part1

http://blog.csdn.net/u011095253/article/details/9158387

http://www.voidcn.com/article/p-alabqyxg-ku.html



Tree Related


       return (root->val < getMin(root->right)) && (root->val > getMax(root->left))
            && isValidBST(root->right) && isValidBST(root->left)
      Note: getMin and getMax must return long type value.

100.  Same Tree
        return (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right)

 101 Symmetric Tree
 isSymmetric(TreeNode* root)  call  isMirror(root, root), which
 return (t1->val == t2->val) && isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left);

110  Balanced Binary Tree 
        Utility function depth() to get the depth of a given tree (also DFS)
         return (abs(leftDepth - rightDepth) <= 1) && isBalanced(root->left) && isBalanced(root->right).  (DFS)
104.  Maximum Depth of Binary Tree
    if (!root) return 0;
    Otherwise:
     return max(maxDepth(root->left), maxDepth(root->right)) + 1;

111. Minimum Depth of Binary Tree
        if (!root) return 0;    
        if (!root->left)  return minDepth(root->right) + 1;
        if (!root->right)  return minDepth(root->left) +  1;
        Otherwise:
        return min(minDepth(root->left), minDepth(root->right)) + 1;


108 Convert Sorted Array to Binary Search Tree
call toBST(nums, 0 /* start */, nums.size() - 1 /* end */), in which recursively (DFS) call toBST;

109.  Convert Sorted List to Binary Search Tree
 Same with 108, except you have to use a for loop start from the beginning to find the mid element in the list as the root->val.

112   Path Sum
 Base Case: if (!root->left && !root->right && (root->val == sum)) return true;
 Recursion formula:  return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val)

113.  Path Sum II
    (a) backtracking, keep the cur node list for traversing, push to the result when reach the leaf
          and satisfy conditions, no matter satisfy or not satisfy the condition pop the last element        (backtrack when return from the current level to its caller), DFS.
    (b) You could also don't pop_back() cur, if you pass value of cur (instead of reference) instead.

129 Sum Root to Leaf Numbers

Base Case: Return the value on from root to leaf when reach leaf node
       preSum = preSum * 10 + root->val;
        if (!root->left && !root->right)
            return preSum;

DFS Recursion Formula:
 return DFS(root->left, preSum) + DFS(root->right, preSum);
Caller DFS(root, 0 /*preSum*/);


257. Binary Tree Paths

     When meet leaf node: push back the path into result:
     if (!root->left && !root->right) {
            res.push_back(cur);
            return;
      }
     
      DFS Recursion Formula:
        if (root->left)
            DFS(root->left, res, cur + "->" + to_string(root->left->val));
        if (root->right)
            DFS(root->right, res, cur + "->" + to_string(root->right->val));


 116   Populating Next Right Pointers in Each Node
DFS O(1) space, set root->left->next = root->right; root->right->next = root->next->left
 when cross sub-tree for root. Recursively call connect(root->left) and connect(root->right)
This is safe to do since we already have the root->next connected before going to the child
nodes if we know it is a perfect binary tree.

117. Populating Next Right Pointers in Each Node II
    Note during recursion we must connect the right subtree before the left subtree, otherwise the population would be complete. And also we need a findNext() function to find the next existing node
for the current node at the same level. (in 116, this is simple, we know the root->left->next = root->right, and root->right->next = root->next->left or NULL)


337.  House Robber III
l = rob(root->left), r = rob(root->right)
ll = rob(root->left->left), lr = rob(root->left->right)
rl = rob(root->right->left), rr = rob(root->right->right)
return max(root->val + ll + lr + rl + rr, l + r)
Typical DFS

114.  Flatten Binary Tree to Linked List
preOrder traversal to populate a vector<TreeNode*> with all
tree nodes. In a for loop, set all the left child to NULL and
set the right child to point to its  successor in the vector


515.  Find Largest Value in Each Tree Row
DFS: initialize max value : res[level] = root->val when first time
enter a new level (by res.push_back(root->val)). Update the max val
if find some larger value later at the same level during DFS recursion.



513.  Find Bottom Left Tree Value
DFS (pre,in,post order). pass  reference of leftVal and maxDepth. And pass value of current depth, and the root. When (depth > maxDepth) update the {maxDepth = depth and leftVal = root->val }
Recursively call DFS(root->left, leftVal, depth + 1, maxDepth) and DFS(root->right, leftVal, depth + 1, maxDepth)


105    Construct Binary Tree from Preorder and Inorder Traversal
        (a) Find index of root in the inorder list. (Note: the for loop condition be "<=" rather that "<",
              since the right subtree could be null, i.e: (root is the last element in inorder)
        TreeNode* root = new TreeNode(preorder[preBegin]);
        (b) root->left = constructTree(preorder, preBegin + 1,  preBegin + 1 + (index - 1 - inBegin),
                                   inorder, inBegin, index - 1);
             root->right = constructTree(preorder, preEnd - (inEnd - index - 1),  preEnd,
                                   inorder, index + 1, inEnd);

106.  Construct Binary Tree from Inorder and Postorder Traversal
  (a) Find index of root in the inorder list.
       TreeNode* root = new TreeNode(inorder[index]);
        root->left = constructTree(inorder, inBegin, index - 1,
                                   postorder, postBegin, postBegin + (index - 1 - inBegin));
        root->right = constructTree(inorder, index + 1, inEnd,
                                   postorder, postEnd - 1 - (inEnd - index - 1), postEnd - 1);


199  Binary Tree Right Side View
        DFS the tree in order of root-->right-->left
       (a) Pass around a reference of int array (like vector<int>& res) and the current level by value as well as the root.
        (b) When reach a new level (i.e: res.size() == level) push_back the value into res.  Increase level by 1 and recursively call the right child and the left child (note call the right child before call the   left child):
         DFS(root->right, res, level + 1)
         DFS(root->left, res, level +   1)




Comments

Post a Comment

Popular posts from this blog

zhitongguigu

Lecture 1: To do: (117? 199) Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree . In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree. numerical_limits<int>::min()   <==> INT_MIN
Read more

Array Part2

Two pointers 977 Squares of a Sorted Array      We can use two pointers to read the positive and negative parts of the array - one pointer  j  in the positive direction, and another  i  in the negative direction. Now that we are reading two increasing arrays (the squares of the elements), we can merge these arrays together using a two-pointer technique. 11 Container With Most Water      O(N) time and O(1) space, since better candidadates must use the taller line of l and r therefore we can use two pointer keep moving towards each other until they meet. Always abandon the shorter line while moving. 80 Remove Duplicates from Sorted Array II      tail = 0; for (int i = 0;  i < nums.size(); i++)           if (i < 2 || nums[i] > nums[tail - 2]) // not included twice yet                 nums[tail++] = nums...
Read more

Two pointers (Part 1)

344 Reverse String      Use two pointers i, j. keep switching elements at position i, j while i < j.     string reverseString(string s) {        for (int i = 0, j = s.size() - 1; i < j; i++, j--)            swap(s[i], s[j]);                  return s;     } 345 Reverse Vowels of a String      Similar with 344  Reverse String ,  except we need to guard the swap operation conditionally based on whether the current two chars are vowels or not. 283 Move Zeroes      Use two pointers, the front iterates the elements in the array. while the tail one keeps the current store position. If front is not zero, store it to the tail position and increase tail pointer. After the loop, set all the remaining with zero. 349 Intersection of Two Arrays      ...
Read more