PINEAL.ME   Archives  About

Binary Tree

Intro

Concepts

  1. Full Binary Tree: 全部都填满的树。

  2. Complete Binary Tree: 除了最后一行其他都填满,最后一行的最后一个之前(左边)全部是满的。

  3. Balanced Binary Tree: 左右子树的高度最多差1. Height of the tree: $O(log(n))$

  4. Binary Search Tree: Recursively, Leftsubtree is smaller than root and righ subtree is larger than root. Inorder traverse is increasing.

Traverse

Example

example

Traverse Recursively

void helper(TreeNode* node, vector<int> & rst){
    if (node != nullptr){
//      rst.emplace_back(root -> val);  If it is PreOder
        helper(node -> left, rst);
//      rst.emplace_back(root -> val);  If it is InOrder
        helper(node -> right, rst);
//      rst.emplace_back(root -> val);  If it is PostOrder
    }
}
vector<int> DFS_Traversal(TreeNode* root) {
    // write your code here
    vector<int> rst;
    helper(root, rst);
    return rst;
}

Preorder iterative

void pushleft(TreeNode* root, stack<TreeNode*> & s, vector<int> & res) {
    while (root) {
        res.emplace_back(root->val);
        s.push(root);
        root = root->left;
    }
}

vector<int> preorder(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> s;
    pushleft(root, s, res);
    while (!s.empty()) {
        auto cur = s.top();
        s.pop();
        cur = cur->right;
        pushleft(cur, s, res);
    }
    return res;
}

Inorder Iterative

void pushleft(TreeNode* root, stack<TreeNode*> & s) {
    while (root) {
        s.push(root);
        root = root->left;
    }
}

vector<int> inorder(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> s;
    pushleft(root, s);
    while (!s.empty()) {
        auto cur = s.top();
        s.pop();
        res.emplace_back(cur->val);
        cur = cur->right;
        pushleft(cur, s);
    }
    return res;
}

Postorder iterative I

vector<int> postorder(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> s1, s2;
    s1.push(root);
    while (!s1.empty()) {
        auto cur = s1.top();
        s2.push(cur);
        s1.pop();
        if (cur->left) {
            s1.push(cur->left);
        }
        if (cur->right) {
            s1.push(cur->right);
        }
    }
    while (!s2.empty()) {
        auto cur = s2.top();
        s2.pop();
        res.emplace_back(cur->val);
    }
    return res;
}

Postorder iterative II

vector<int> postorderII(TreeNode* root) {
    if (root == nullptr) {
        return {};
    }
    vector<int> res;
    stack<TreeNode*> s;
    s.push(root);
    TreeNode* prev = nullptr;
    while (!s.empty()) {
        auto cur = s.top();
        if (prev == nullptr || cur == prev->left || cur == prev->right) {
            if (cur->left) {
                s.push(cur->left);
            }
            else if (cur->right) {
                s.push(cur->right);
            }
            else {
                s.pop();
                res.emplace_back(cur->val);
            }
        }
        else if (prev == cur->right || prev == cur->left && cur->right == nullptr) {
            s.pop();
            res.emplace_back(cur->val);
        }
        else {
            s.push(cur->right);
        }
        prev = cur;
    }
    return res;
}

BFS level order

vector<vector<int>> levelOrder(TreeNode *root) {
    vector<vector<int>> rst;
    if (root == nullptr) return rst;

    queue<TreeNode*> nodes;
    nodes.push(root);

    while(!nodes.empty()){
        vector<int> level;
        int size = nodes.size();
        for (int i = 0; i < size; i++){
            TreeNode* node = nodes.front();
            nodes.pop();
            level.emplace_back(node -> val);
            if (node -> left != nullptr) nodes.push(node -> left);
            if (node -> right != nullptr) nodes.push(node -> right);    
        }
        rst.emplace_back(level);
    }
return rst;    
}

Morris Traverse(TODO)

Binary Tree Iterator

Implementation

Link

BST iterator

class BSTIterator {
private:
    stack<TreeNode*> s;
public:
    BSTIterator(TreeNode *root) {
        while (root) {
            s.push(root);
            root = root -> left;
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !s.empty();
    }

    /** @return the next smallest number */
    //which means ascending order
    //which means inoredr traversal
    int next() {
        if (s.empty()) {
            return INT_MAX;
        }
        
        TreeNode* parent = s.top();
        s.pop();
        TreeNode* cur = parent -> right;
        while (cur) {
            s.push(cur);
            cur = cur -> left;
        }
        return parent -> val;
    }
};

Different views of tree

Boundary of Binary Tree

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> boundaryOfBinaryTree(TreeNode* root) {
        if (root == nullptr) {
            return {};
        }
        vector<int> left, right, bottom, res;
        res.emplace_back(root->val);
        getLeft(root->left, left);
        getBottom(root->left, bottom);
        getBottom(root->right, bottom);
        getRight(root->right, right);
        res.insert(res.end(), left.begin(), left.end());
        res.insert(res.end(), bottom.begin(), bottom.end());
        res.insert(res.end(), right.rbegin(), right.rend());
        return res;
    }
private:    
    void getLeft(TreeNode* root, vector<int> & res) {
        if (root == nullptr) {
            return;
        }
        if (!root->left && !root->right) {
            return;
        }
        
        res.emplace_back(root->val);
        if (root->left) {
            getLeft(root->left, res);
        }
        else {
            getLeft(root->right, res);    
        }
    }
    
    void getRight(TreeNode* root, vector<int> & res) {
        if (root == nullptr) {
            return;
        }
        if (!root->left && !root->right) {
            return;
        }
        res.emplace_back(root->val);
        if (root->right) {
            getRight(root->right, res);
        } 
        else {
            getRight(root->left, res);
        }
    }
    
    void getBottom(TreeNode* root, vector<int> & res) {
        if (root == nullptr) {
            return;
        }
        if (!root->left && !root->right) {
            res.emplace_back(root->val);
        }
        getBottom(root->left, res);
        getBottom(root->right, res);
    }
};

Path problems

Maximum Path Sum Binary Tree I

Given a binary tree in which each node contains an integer number. Find the maximum possible sum from one leaf node to another leaf node. If there is no such path available, return INT_MIN (C++).

class Solution {
 public:
 int global_max = INT_MIN;
 
  int maxPathSum(TreeNode* root){
    dfs(root);
    return global_max;
  }
 
  int dfs(TreeNode* root) {
    if (root == nullptr) {
      return 0;
    }
  
    int left =  dfs(root -> left);
    int right = dfs(root -> right);

    if (root -> left && root -> right) {
      int sum = left + right + root -> value;
      global_max = max(sum, global_max);
      return max(left, right) + root -> value;
    } 
      return (!root -> left)? right + root -> value : left + root -> value;
  }
};

Maximum Path Sum Binary Tree II

Given a binary tree in which each node contains an integer number. Find the maximum possible sum from any node to any node (the start node and the end node can be the same).

class Solution {
 public:
  int maxPathSum(TreeNode* root) {
    int global_max = INT_MIN;
    dfs(root, global_max);    
    return global_max;
  }
  
  int dfs(TreeNode* root, int& global_max) {
    if (root == nullptr) {
      return 0;
    }
    int left = dfs(root -> left, global_max);
    int right = dfs(root -> right, global_max);
    //left = (left < 0)? 0 : left;
    //right = (right < 0)? 0 : right; 
    global_max = max(global_max, left + right + root -> value);
    return max(0, max(left, right) + root -> value); 
  }
};

Maximum Path Sum Binary Tree III

Given a binary tree in which each node contains an integer number. Find the maximum possible subpath sum(both the starting and ending node of the subpath should be on the same path from root to one of the leaf nodes, and the subpath is allowed to contain only one node).

class Solution {
 public:
  int maxPathSum(TreeNode* root) {
    int global_max = INT_MIN;
    dfs(root, global_max);
    return global_max;
  }
  
  int dfs(TreeNode* root, int& global_max) {
    if (root == nullptr) {
      return 0;
    }
    int left = dfs(root -> left, global_max);
    int right = dfs(root -> right, global_max);
    int sum = max(max(left, right) , 0) + root -> value;
    global_max = max(global_max, sum);
    return sum;
  }
};

LCA problems

LCA I

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || root == p || root == q) {
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root -> left, p, q);
        TreeNode* right = lowestCommonAncestor(root -> right, p, q);
        if (left && right) {
            return root;
        }
        return left? left : right;
    }

LCA of BST

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) {
            return root;
        // p, q are in two sides or root is one of p, q
        } else if ((root->val - p->val) * (root->val - q->val) <= 0) {
            return root;
        //p,q are smaller than root => both in left side
        } else if (root->val > p->val && root -> val > q->val) {
            return lowestCommonAncestor(root->left, p, q);
        //both in right side
        } else {
            return lowestCommonAncestor(root->right, p, q);            
        }
    }

LCA II

Give the treenode with parent pointer.

//class TreeNodeP {
// public:
//  int value;
//  TreeNodeP* left;
//  TreeNodeP* right;
//  TreeNodeP* parent;
//  TreeNodeP(int v, TreeNodeP* p) 
//      : value(v), left(NULL), right(NULL), parent(p) {}
//};

class Solution {
private:
 int path_length(TreeNodeP* node) {
   int length = 0;
   while (node) {
     node = node -> parent;
     length++;
   }
   return length;
 }
 
 TreeNodeP* llc(TreeNodeP* small, TreeNodeP* large, int diff) {
   while (diff > 0) {
     large = large -> parent;
     diff--;
   }
   while (large != small) {
     large = large -> parent;
     small = small -> parent;
   }
   return large;
 }
 public:
  TreeNodeP* LCA(TreeNodeP* one, TreeNodeP* two) {
    int l1 = path_length(one);
    int l2 = path_length(two);
    if (l1 <= l2) {
      return llc(one, two, l2 - l1);
    } else {
      return llc(two, one, l1 - l2);
    }
  }
  
};

LCA III

Given two nodes in a binary tree, find their lowest common ancestor (the given two nodes are not guaranteed to be in the binary tree). Return null If any of the nodes is not in the tree. There is no parent pointer for the nodes in the binary tree. The given two nodes are not guaranteed to be in the binary tree.

class Solution {
 public:
  bool flag1 = false;
  bool flag2 = false;
  TreeNode* solve(TreeNode* root, TreeNode* one, TreeNode* two) {
  
    traversal(root, one, two);
    if (flag1 && flag2) {
      return findLCA(root, one, two);
    } 
    return nullptr;
  }
  void traversal(TreeNode* root, TreeNode* one, TreeNode* two) {
    if (root == nullptr) {
      return;
    }
    if (root == one) {flag1 = true;}
    if (root == two) {flag2 = true;}
    traversal(root -> left, one, two);
    traversal(root -> right, one, two);
  }
  TreeNode* findLCA(TreeNode* root, TreeNode* one, TreeNode* two) {
   
    if (root == nullptr) {
      return nullptr;
    }
    
    if (root == one) {
      return root;
    }
    
    if (root == two) {
      return root;
    }
    
    auto left =  findLCA(root -> left,  one, two);
    auto right = findLCA(root -> right, one, two);
    
    if (left && right) {
      return root;
    } else if (left) {
      return left;
    } else if (right) {
      return right;
    } else {
      return nullptr;
    }
  }
};

LCA IV

Give k nodes, find their CLA.

class Solution {
 public:
  TreeNode* LCA(TreeNode* root, vector<TreeNode*> nodes) {
    if (root == nullptr) {
      return root;
    }
    
    for (int i = 0; i < nodes.size(); i++) {
      if (root == nodes[i]) {
        return root;
      }
    }
    
    auto left = LCA(root -> left, nodes);
    auto right = LCA(root -> right, nodes);
    
    if (left && right) {
      return root;
    } else {
      return left? left : right;
    }
  }
};

Check if cousins

Geeksforgeeks source

bool checkIfCousins(TreeNode* root, TreeNode* one, TreeNode* two) {
  
  bool res = false;
  helper(root, one, two, 0, res);
  return res;
}

//return target'node level
//return -1 is not found
int helper(TreeNode* root, TreeNode* one, TreeNode* Two, int level, bool & res) {

  if (root == nullptr) {
    return -1;
  }

  if (root == one || root == two) {
    return level;
  }

  int left = helper(root->left, one, two, level + 1, res);
  int right = helper(root->right, one, two, level + 1, res);

  if (left == right && left - 1 > level) {
    res = true;
  }
  return max(left, right);
}

Serialize and deserialize binary tree

Reconstruct Binary Tree With Preorder And Inorder

一棵树需要什么信息?需要知道什么是根,左子树和右子树分别又是什么。

那么从这两种遍历之中可以获取什么信息?

先序遍历: root | left subtree | right subtree

中序遍历: left subtree | root | right subtree

先序遍历的最左边,一定是根,但是无法找到左子树和右子树的分界点;但是可以通过找到根,从而从中序遍历中找到这个分界。

解题步骤:

  1. leftmost of preOrder must be root

  2. find position of root in inOrder => need a hashtable to pre-store indices

  3. in inorder: left side of root is left subtree

  4. in inorder: right side of root is right subtree

  5. recursively solve the problem on left subtree and right subtree

  TreeNode* reconstruct(vector<int> in, vector<int> pre) {
    unordered_map<int, int> table;
    for (int i = 0; i < in.size(); i++) {
      table[in[i]] = i;
    }
    
    return helper(in, 0, in.size() - 1, pre, 0, table);
  }
  
  TreeNode* helper(const vector<int> & in, int in_left, int in_right, 
                   const vector<int> & pre, int pre_left,
                    unordered_map<int, int> table) {
                      
    if (in_left > in_right) {
      return nullptr;
    }
    
    TreeNode* root = new TreeNode(pre[pre_left]);
    int index = table[root -> value];
    root -> left = helper(in, in_left, index - 1, pre, pre_left + 1, table);
    root -> right = helper(in, index + 1, in_right, pre, pre_left + index - in_left + 1, table);
    return root;                  
	}

Reconstruct with level order

level order 的第一个元素,一定是root。通过inorder找到root的位置,然后根据index的关系,分割左右子树。

class Solution {
 public:
  TreeNode* reconstruct(vector<int> in, vector<int> level) {
    map<int, int> table;
    for (int i = 0; i < in.size(); i++) {
      table[in[i]] = i;
    }
    return helper(level, table);
  }
  TreeNode* helper(vector<int> level, map<int, int> table) {
    if (level.size() == 0) {
      return nullptr;
    }
    TreeNode* root = new TreeNode(level[0]);
    int index = table[root->value];
    vector<int> left;
    vector<int> right;
    
    for (int i = 0; i < level.size(); i++) {
      if (table[level[i]] < index) {
        left.emplace_back(level[i]);
      } else if (table[level[i]] > index) {
        right.emplace_back(level[i]);
      }
    }
    root -> left = helper(left, table);
    root -> right = helper(right, table);
    return root;
  }
};

Reconstruct Binary Search Tree With Postorder Traversal

class Solution {
 public:
  TreeNode* reconstruct(vector<int> post) {
    //Post order -> [leftsubtree][rightsubtree]root => determine the position of root
    //In   order -> [left]root[right] =>recursively find left and right parts
    vector<int> in(post);
    sort(in.begin(), in.end());
    unordered_map<int, int> table;
    for (int i = 0; i < in.size(); i++) {
        table[in[i]] = i;
    }
    return helper(in, post, table, post.size() - 1, 0, in.size() - 1);
  }
  
  TreeNode* helper(vector<int> in, vector<int> post, unordered_map<int, int> & table,
                    int post_right, int in_left, int in_right) {
  
    if (in_left > in_right){
      return nullptr;
    }
    
    TreeNode* root = new TreeNode(post[post_right]);
    int index = table[root -> value];
    
    root -> right = helper(in, post, table, post_right - 1, index + 1, in_right);
    root -> left = helper(in, post, table, post_right - 1 - (in_right - index), in_left, index - 1);
    return root;
  }
};
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string order;
        inorderDFS(root, order);
        return order;
    }
    
    inline void inorderDFS(TreeNode* root, string& order) {
        if (!root) return;
        char buf[4];
        memcpy(buf, &(root->val), sizeof(int)); //burn the int into 4 chars
        for (int i=0; i<4; i++) order.push_back(buf[i]);
        inorderDFS(root->left, order);
        inorderDFS(root->right, order);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int pos = 0;
        return reconstruct(data, pos, INT_MIN, INT_MAX);
    }
    
    inline TreeNode* reconstruct(const string& buffer, int& pos, int minValue, int maxValue) {
        if (pos >= buffer.size()) return NULL; //using pos to check whether buffer ends is better than using char* directly.
        
        int value;
        memcpy(&value, &buffer[pos], sizeof(int));
        if (value < minValue || value > maxValue) return NULL;
        
        TreeNode* node = new TreeNode(value);
        pos += sizeof(int);
        node->left = reconstruct(buffer, pos, minValue, value);
        node->right = reconstruct(buffer, pos, value, maxValue);
        return node;
    }
};

Create a Doubly Linked List from a Ternary Tree

Question source

FAQ

Difference between DFS and BFS

DFS using stacks, and BFS using queues if Non-Recursion

Difference between Recursion and Non-Recursion

Recursion is dangerous when memory resource is limited: stack may overflow; However Non-Recursion method occupies more space

Binary Tree