မှတ်ချက် – ဒီ Post သည် Algorithm Interview Preparation အပိုင်းဆက်ဖြစ်သည်။

ကျနော်တို့ဒီနေ့ရှင်းမယ့် ပြဿနာက 1026. Maximum Difference Between Node and Ancestor ဆိုတဲ့ leetcode question ဘဲဖြစ်ပါတယ်။

Given the root of a binary tree, find the maximum value v for which there exist different nodes a and b where v = |a.val - b.val| and a is an ancestor of b.

A node a is an ancestor of b if either: any child of a is equal to b or any child of a is an ancestor of b.

Example 1:

        8
       /  \
      3   10
     / \    \
    1   6   14
       / \   /
      4   7 13

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation: We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.

Example 2:

    1
     \
      2
     / \
    0   3

Input: root = [1,null,2,null,0,3]
Output: 3
 

Constraints:

The number of nodes in the tree is in the range [2, 5000].
0 <= Node.val <= 105

------------------------------------------------------------------------

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxAncestorDiff = function(root) {
    
};

မေးခွန်းက binary tree ပေးထားမယ်။ ancestor နဲ့ descendant nodes တွေထဲကအကြီးဆုံး difference ကိုရှာပါတဲ့။

ဒီပြဿနာကိုဖြေရှင်းဖို့ဆိုရင် binary tree သိရမယ်။ binary tree traversal ဘယ်လိုလုပ်ရလဲသိရမယ်။ ကျနော်တို့အဖြေက Depth-First Seach (DFS) ကိုသုံးထားတယ်။

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

function buildTree(arr) {
    if (!arr.length) return null;

    let root = new TreeNode(arr[0]);
    let queue = [root];

    for (let i = 1; i < arr.length; i++) {
        let parent = queue[0]; // Get the current parent

        if (i % 2 === 1) { // Left child
            if (arr[i] !== null) {
                parent.left = new TreeNode(arr[i]);
                queue.push(parent.left);
            }
        } else { // Right child
            if (arr[i] !== null) {
                parent.right = new TreeNode(arr[i]);
                queue.push(parent.right);
            }
            queue.shift(); // Remove the processed parent
        }
    }

    return root;
}


/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxAncestorDiff = function(root) {
  const traverse = (node, max, min) => {
    if(!node) return max - min; 
        
    max = Math.max(max, node.val);
    min = Math.min(min, node.val);
        
    return Math.max(traverse(node.left, max, min), traverse(node.right, max, min));
  }
  
  return traverse(root, root.val, root.val);
};

// build the tree from the array
let treeArray = [8,3,10,1,6,null,14,null,null,4,7,13];
let root = buildTree(treeArray);

maxAncestorDiff(root)

TreeNode ကကျနော်တို့ binary tree node အတွက်။ နောက် buildTree ဆိုတာ စမ်းကြည့်ပီး code ကို execute လုပ်ပီး debugger ထောက်တကြောင်းချင်းကြည့်ချင်တဲ့သူတွေအတွက် array ကနေ binary tree build လုပ်တဲ့ function ပေါ့။ maxAncestorDiff ကတော့ကျနော်တို့ DFS နှင့်ဖြေထားတဲ့အဖြေပေါ့။