算法及数据结构系列 - 树

系列文章目录
算法及数据结构系列 - 二分查找
算法及数据结构系列 - BFS算法
算法及数据结构系列 - 动态规划
算法及数据结构系列 - 双指针
算法及数据结构系列 - 回溯算法

树

框架

树遍历框架

/* 基本的二叉树节点 */
class TreeNode {int val;TreeNode left, right;
}void traverse(TreeNode root) {// 前序遍历traverse(root.left)// 中序遍历traverse(root.right)// 后序遍历
}

N叉树遍历框架

/* 基本的 N 叉树节点 */
class TreeNode {int val;TreeNode[] children;
}void traverse(TreeNode root) {for (TreeNode child : root.children)traverse(child)
}

经典题型

124.二叉树的最大路径和

相似问题：
687. 最长同值路径
543. 二叉树直径
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
思路：后序遍历；递归；在递归中计算
递归函数helper(root)定义: 以root为起点，向下延伸的路径和的最大值

class Solution {int res = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {helper(root);return res;}public int helper(TreeNode root){if(root == null){return 0;}int maxLeft = helper(root.left);maxLeft = maxLeft < 0 ? root.val : root.val + maxLeft;int maxRight = helper(root.right);maxRight = maxRight < 0 ? root.val : root.val + maxRight;res = Math.max(res, maxLeft + maxRight - root.val);return Math.max(maxLeft, maxRight);}
}

105.从前序与中序遍历序列构造二叉树

提示：使用map记录中序数组位置

TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap) {if(preStart > preEnd || inStart > inEnd) return null;TreeNode root = new TreeNode(preorder[preStart]);int inRoot = inMap.get(root.val);int numsLeft = inRoot - inStart;root.left = buildTree(preorder, preStart + 1, preStart + numsLeft, inorder, inStart, inRoot - 1, inMap);root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd, inorder, inRoot + 1, inEnd, inMap);return root;
}

恢复二叉搜索树

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

提示：中序遍历, 逆序对, 双指针

class Solution {TreeNode first = null;TreeNode second = null;public void recoverTree(TreeNode root) {inorderTraversal(root);int temp = first.val;first.val = second.val;second.val = temp;}TreeNode pre = null;private void inorderTraversal(TreeNode root) {if (root == null) {return;}inorderTraversal(root.left); /*******************************************************/if(pre != null && root.val < pre.val) {//第一次遇到逆序对if(first==null){first = pre;second = root;//第二次遇到逆序对}else{second = root;}}pre = root; /*******************************************************/inorderTraversal(root.right);}
}

刷题

112.路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点; 注意有可能有负数

public class Solution {public boolean hasPathSum(TreeNode root, int sum) {if(root == null) return false;if(root.left == null && root.right == null && sum - root.val == 0) return true; // 到叶子节点return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);}
}

113.路径总和 II

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
思路：回溯算法，路径/当前可选择/选择及撤销选择

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {List<List<Integer>> res = new ArrayList<List<Integer>>();public List<List<Integer>> pathSum(TreeNode root, int sum) {List<Integer> path = new ArrayList<Integer>();if(root != null){path.add(root.val);}recurve(root, sum, path);return res;}public void recurve(TreeNode root, int sum, List<Integer> path){if(root == null){return;}if(root.left == null && root.right == null && sum == root.val){// 到叶子节点res.add(new ArrayList<Integer>(path));return;}if(root.left != null){path.add(root.left.val);recurve(root.left, sum - root.val, path);path.remove(path.size() - 1);}if(root.right != null){path.add(root.right.val);recurve(root.right, sum - root.val, path);path.remove(path.size() - 1);}}
}

437.路径总和 III

给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

思路一: DFS

每个节点为根节点，都算一遍路径和为sum的有几条，然后加起来
helper(root,sum): 以root为起点的路径和为sum的路径数

class Solution {public int pathSum(TreeNode root, int sum) {if(root == null) return 0;return helper(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);}int helper(TreeNode root, int sum){if(root == null) return 0;sum -= root.val;return (sum == 0 ? 1 : 0) + helper(root.left, sum) + helper(root.right, sum);}
}

思路二: 前缀和

思路一很明显效率不够高，存在大量重复计算。
所以第二种做法，采取了类似于数组的前n项和的思路。对于树的话，采取DFS加回溯，每次访问到一个节点，把该节点加入到当前的pathSum中，然后判断是否存在一个之前的前n项和，其值等于pathSum与sum之差。如果有，就说明现在的前n项和，减去之前的前n项和，等于sum，那么也就是说，这两个点之间的路径和，就是sum。最后要注意的是，记得回溯，把路径和弹出去。

class Solution {public int pathSum(TreeNode root, int sum) {HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); // 记录路径和->次数map.put(0, 1);return helper(root, map, sum, 0);}int helper(TreeNode root, HashMap<Integer, Integer> map, int sum, int pathSum){int res = 0;if(root == null) return 0;pathSum += root.val;res += map.getOrDefault(pathSum - sum, 0);map.put(pathSum, map.getOrDefault(pathSum, 0) + 1);res = helper(root.left, map, sum, pathSum) + helper(root.right, map, sum, pathSum) + res;map.put(pathSum, map.get(pathSum) - 1); // 弹出return res;}
}

687. 最长同值路径

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
思路：后序遍历、递归
关键是递归函数helper(node)定义：从节点node能够延伸出的最长同值路径；在递归进行中计算

class Solution {int res = 0;public int longestUnivaluePath(TreeNode root) {helper(root);return res;}int helper(TreeNode root){if(root == null) return 0;int left = helper(root.left);int right = helper(root.right);left = (root.left != null && root.left.val == root.val) ? left + 1 : 0;right = (root.right != null && root.right.val == root.val) ? right + 1 : 0;res = Math.max(res, left + right);// 在递归中计算return Math.max(left, right);}
}

543. 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
思路：后序遍历、递归
关键是递归函数depth(node)定义：从节点node能够延伸出的最长路径；在递归进行中计算

class Solution {int maxd=0;public int diameterOfBinaryTree(TreeNode root) {depth(root);return maxd;}public int depth(TreeNode node){if(node==null){return 0;}int Left = depth(node.left);int Right = depth(node.right);//将每个节点最大直径(左子树深度+右子树深度)当前最大值比较并取大者maxd=Math.max(Left+Right,maxd);return Math.max(Left,Right)+1;//返回节点深度}
}

95. 不同的二叉搜索树

给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。

public class Solution {public List<TreeNode> generateTrees(int n){int from = 1;int to = n;return genTree(from,to);}public List<TreeNode> genTree(int from,int to){List<TreeNode> treeNodeList = new ArrayList<TreeNode>();if(from == to){TreeNode treeNode = new TreeNode(from);treeNodeList.add(treeNode);return treeNodeList;}for(int i=from;i<=to;i++){int leftFrom = from;int leftTo = i-1;List<TreeNode> leftNodes = new ArrayList<TreeNode>();if(leftFrom <= leftTo){leftNodes = genTree(leftFrom,leftTo);}int rightFrom = i+1;int rightTo = to;List<TreeNode> rightNodes = new ArrayList<TreeNode>();if(rightFrom <= rightTo){rightNodes = genTree(rightFrom,rightTo);}if(leftNodes.size() == 0 && rightNodes.size() == 0){TreeNode treeNode = new TreeNode(i);treeNodeList.add(treeNode);}else if(leftNodes.size() == 0){for (TreeNode rightNode:rightNodes) {TreeNode treeNode = new TreeNode(i);treeNode.right = rightNode;treeNodeList.add(treeNode);}}else if(rightNodes.size() == 0){for (TreeNode left:leftNodes) {TreeNode treeNode = new TreeNode(i);treeNode.left = left;treeNodeList.add(treeNode);}}else{for (TreeNode leftNode:leftNodes) {for (TreeNode rightNode:rightNodes) {TreeNode treeNode = new TreeNode(i);treeNode.left = leftNode;treeNode.right = rightNode;treeNodeList.add(treeNode);}}}}return treeNodeList;}
}

98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

提示： 中序遍历

class Solution {boolean res = true;TreeNode pre = null;public boolean isValidBST(TreeNode root) {helper(root);return res;}public void helper(TreeNode root){if(root == null){return;}helper(root.left);if(pre != null && pre.val >= root.val){res = false;return;}pre = root;helper(root.right);}
}

94. 二叉树的中序遍历

递归算法

class Solution {List<Integer> res = new ArrayList<Integer>();public List<Integer> inorderTraversal(TreeNode root) {helper(root);return res;}public void helper(TreeNode root){if(root == null){return;}helper(root.left);res.add(root.val);helper(root.right);}
}

迭代算法
提示：栈, 举个栗子尝试一下就知道了

class Solution {Stack<TreeNode> s = new Stack<TreeNode>();List<Integer> res = new ArrayList<Integer>();public List<Integer> inorderTraversal(TreeNode root) {if(root == null){return res;}s.push(root);TreeNode l = root.left;while(l != null){s.push(l);l = l.left;}while(!s.isEmpty()){TreeNode tmp = s.pop();res.add(tmp.val);TreeNode r = tmp.right;while(r != null){s.push(r);r = r.left;}}return res;}
}

144. 二叉树的前序遍历

迭代算法
提示：栈, 举个栗子尝试一下就知道了

class Solution {Stack<TreeNode> s = new Stack<TreeNode>();List<Integer> res = new ArrayList<Integer>();public List<Integer> preorderTraversal(TreeNode root) {if(root == null){return res;}while(root != null){res.add(root.val);s.push(root);root = root.left;}while(!s.isEmpty()){TreeNode tmp = s.pop();TreeNode r = tmp.right;while(r != null){res.add(r.val);s.push(r);r = r.left;}}return res;}
}