[Javascript] DFS solution without optimization


  • 0
    P

    Let's say sum(tree) is sum. The tree can be partitioned if sum(subTree) is sum/2.

    1. A sum function to calculate sum of a tree.
            var sumTree = function (root) {
              if (root == null) {
                return 0;
              }
              return root.val + sumTree(root.left) + sumTree(root.right);
            }; 
    

    2.A partition function to enumerate all subTrees.

            var partition = function (root, half) {
    
              function dfs(node) {
                if (node.left) {
                  if (sumTree(node.left) === half) {
                    return true;
                  } else {
                    if (dfs(node.left)) {
                      return true;
                    }
                  }
                }
    
                if (node.right) {
                  if (sumTree(node.right) === half) {
                    return true;
                  } else {
                    if (dfs(node.right)) {
                      return true;
                    }
                  }
                }
              }
    
              const result = dfs(root);
              return !!result;
            };
    
    1. Let's find out.
            var checkEqualTree = function (root) {
              const sum = sumTree(root);
              return sum % 2 !== 0 ? false : partition(root, sum / 2);
            };
    

    Some optimization suggestions:
    1.Cache the sum of sum(subTrees).
    2.Please add comments if you have more.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.