本文主要是介绍get (tree node val - (subtree val sum))，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给一个tree，返回每个点左右子树的和与自己值的差，用递归做，还问了不递归怎么做
package tree;import java.util.*;import z_dataStructure.TreeNode;public class TreeNodeMinusSubtreeSum {public static void main(String[] args) {TreeNode root = new TreeNode(1);TreeNode node2 = new TreeNode(2);TreeNode node3 = new TreeNode(3);TreeNode node4 = new TreeNode(4);TreeNode node5 = new TreeNode(5);root.left = node2;root.right = node3;node3.left = node4;node3.right = node5;for (int subsum : treeNodeWithSubtreeSum(root)) {System.out.println(subsum);}ArrayList<Integer> res = new ArrayList<Integer>();treeNodeWithSubtreeSum1(root, res);for (int subsum : res) {System.out.println(subsum);}}public static int treeNodeWithSubtreeSum1(TreeNode root, ArrayList<Integer> res){if (root == null) {return 0;}int leftSubtree = treeNodeWithSubtreeSum1(root.left, res);int rightSubtree = treeNodeWithSubtreeSum1(root.right, res);int sum = root.val - leftSubtree - rightSubtree;res.add(sum);return root.val + leftSubtree + rightSubtree;}public static ArrayList<Integer> treeNodeWithSubtreeSum(TreeNode root) {ArrayList<Integer> ret = new ArrayList<Integer>();if (root == null)return ret;Stack<TreeNode> s = new Stack<TreeNode>();HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();s.add(root);TreeNode pre = null;while (!s.isEmpty()) {TreeNode cur = s.peek();if (pre == null || pre.left == cur || pre.right == cur) {if (cur.left != null) {s.push(cur.left);} else if (cur.right != null) {s.push(cur.right);} else {s.pop();map.put(cur.val, 0);ret.add(cur.val - map.get(cur.val));}} else if (cur.left == pre) {if (cur.right != null) {map.put(cur.val, map.get(pre.val) + pre.val);s.push(cur.right);} else {s.pop();map.put(cur.val, map.get(pre.val) + pre.val);ret.add(cur.val - map.get(cur.val));}} else if (cur.right == pre) {s.pop();int tmp = 0;if (map.containsKey(cur.val))tmp = map.get(cur.val);tmp += map.get(pre.val) + pre.val;map.put(cur.val, tmp);ret.add(cur.val - map.get(cur.val));}pre = cur;}return ret;}
}
这篇关于get (tree node val - (subtree val sum))的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
