二叉树算法

基础知识

二叉树类型：

1. 满二叉树：节点有两个子节点，且每一层都填满
2. 完全二叉树：左顺序二叉树，每一层节点从最左节点依次开始
3. 二叉搜索树：有序二叉树，节点的左子树节点<节点值<节点的右子树节点
4. 平衡二叉搜索树：二叉搜索树+平衡（左右子树高度差<=1）

存储方式：链表/数组

遍历方式：

深度优先遍历DFS（递归法，迭代法）：先往深处走，遇到空节点再往回走  数据结构：栈，先进后出（递归法，迭代法）

• 前序遍历：中左右
• 中序遍历：左中右
• 后序遍历：左右中

观察：前中后，分别对应中的位置不同，其次一左一右；

广度优先遍历BFS（迭代法）：一层一层遍历 数据结构：队列 先进先出

• 层次遍历

节点定义

    class TreeNode{int val;TreeNode left,right;TreeNode(){}TreeNode(int val){this.val = val;}TreeNode(int val,TreeNode left,TreeNode right){this.val = val;this.left = left;this.right = right;}}

算法思路：

1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

DFS

二叉树的前中后序遍历

    public List<Integer> inorderTraversal(TreeNode root){// 1.递归参数和返回值 入参 root 出参 resList<Integer> res = new ArrayList<Integer>();inorder(root,res);return res;}public void inorder(TreeNode root,List<Integer> res){// 2.终止条件  遇到节点if(root == null){return;}// 3.单层递归逻辑res.add(root.val);  // 前序遍历inorder(root.left, res);
//        res.add(root.val);  // 中序遍历inorder(root.right,res);
//        res.add(root.val);  // 后序遍历}

二叉树的最大深度

返还数值的一般都是全局单独定义

    private  int ans = 0;public int maxDepth(TreeNode root){// 1.递归的入参和出参dfs(root,0);return ans;}public void dfs(TreeNode root,int depth){// 2.终止条件if(root == null){return;}// 3。单层递归逻辑depth++;ans = Math.max(ans,depth);dfs(root.left,ans);dfs(root.right,ans);}

翻转二叉树

   public TreeNode invertTree(TreeNode root){dfs(root);return root;}public void dfs(TreeNode root){if(root == null){return;}// 节点互换TreeNode temp = root.left;root.left = root.right;root.right = temp;// 递归dfs(root.left);dfs(root.right);}

对称二叉树

   public boolean isSymmetric(TreeNode root){if(root == null){return true;}else {return dfs(root.left,root.right);}}public boolean dfs(TreeNode left,TreeNode right){if(left == null && right == null){return true;}if(left == null || right == null || left.val!=right.val){return false;}return dfs(left.right,right.left) && dfs(left.left,right.right);}

二叉树直径

思路：

    private int ans;public int diameterOfBinaryTree(TreeNode root){dfs(root);return ans;}private int dfs(TreeNode root){if(root == null){return -1;}int leftLen = dfs(root.left)+1;int rightLen = dfs(root.right)+1;ans = Math.max(ans,leftLen+rightLen);return Math.max(leftLen,rightLen);}

有序数组转二叉搜索树（前序遍历）

思路：

  public TreeNode sortedArrayToBST(int[] nums){return dfs(nums,0,nums.length-1);}public TreeNode dfs(int[] nums,int left,int right){if(left > right){return null;}int mid = left+(right-left)/2;TreeNode root = new TreeNode(nums[mid]);root.left = dfs(nums,left,mid-1);root.right = dfs(nums,mid+1,right);return root;}

验证二叉搜索树

思路：

class Solution {public boolean isValidBST(TreeNode root) {return dfs(root, null, null); // 初始时无边界限制}private boolean dfs(TreeNode node, Integer min, Integer max) {if (node == null) {return true;}// 检查当前节点值是否在 (min, max) 范围内if ((min != null && node.val <= min) || (max != null && node.val >= max)) {return false;}// 递归检查左子树（最大值限制为当前节点值）// 递归检查右子树（最小值限制为当前节点值）return dfs(node.left, min, node.val) && dfs(node.right, node.val, max);}
}

二叉搜索树第k小的树

思路：将二叉树转化为数组，并对数组排序，遍历数组到k-1(从0索引)位置；

k--与--k前者先比较后减 后者先减后比较

应该是利用搜索树特性

class Solution {private int k;public int kthSmallest(TreeNode root, int k) {this.k = k;return dfs(root);}private int dfs(TreeNode node){if(node == null){return -1;}int leftRes = dfs(node.left);if(leftRes != -1){return leftRes;}if(--k == 0){return node.val;}return dfs(node.right);}
}

路径和Ⅲ

思路：把每个节点都当作根节点，根节点向下递归寻找符合条件的单边和

双递归

class Solution {public int pathSum(TreeNode root, long targetSum) {if(root == null){return 0;}int ret = rootSum(root,targetSum);ret += pathSum(root.left, targetSum);ret += pathSum(root.right, targetSum);return ret;}public int rootSum(TreeNode root ,long targetSum){int ret = 0;if(root == null){return 0;}int sum = root.val;if(sum == targetSum){ret++;}ret += rootSum(root.left, targetSum - sum);ret += rootSum(root.right, targetSum - sum);return ret;}}

二叉树最近公共先祖

思路：确认节点的左右单边是否包含p或q节点，包含则返回该节点，否则返回为空。

因为单边找不到只能向下继续递归，可已经走到头了，没有节点了，所以其左右子节点为空返回。

class Solution {public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){return dfs(root,p,q);}public TreeNode dfs(TreeNode node, TreeNode p, TreeNode q){// 隐含了如果找不到对应的p，q节点就返还为空// 因为找不到，就会向下继续左右子节点，但二者或单者不存在，因此就返还为空if(node == null){return null;}// 确定p，q所在的节点if(node.val == q.val || node.val == p.val){return node;}TreeNode left = dfs(node.left,p,q);TreeNode right = dfs(node.right,p,q);// 返还公共祖先if( left != null && right != null){return node;}// 返还单边值if(left != null){return left;}else {return right;}}
}

二叉树最大路径和

思路：最大路径和，返还的是int 类型的数，可以定义一个全局变量。确认单边最大值，要与0比较，防止出现负数。当前节点左右单边的最大路径，返回最大左右单边值+当前节点值。

class Solution {public int max = Integer.MIN_VALUE;public int maxPathSum(TreeNode root){dfs(root);return max;}public int dfs(TreeNode root){if(root == null){return 0;}// 递归计算左右子树的最大贡献值（如果为负则舍弃）int left = Math.max(0,dfs(root.left));int right = Math.max(0,dfs(root.right));// 更新全局最大值（当前节点 + 左右子树）int currentMax = root.val+left+right;max = Math.max(max,currentMax);// 返回当前节点的最大贡献值（只能选择左或右子树的一条路径）return root.val+Math.max(left,right);}
}

BFS

适用场景：「层序遍历」、「最短路径」

// 二叉树的层序遍历
void bfs(TreeNode root) {Queue<TreeNode> queue = new ArrayDeque<>();queue.add(root);while (!queue.isEmpty()) {int n = queue.size();for (int i = 0; i < n; i++) { // 变量 i 无实际意义，只是为了循环 n 次TreeNode node = queue.poll();if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}}
}

二叉树层序遍历

   public List<List<Integer>> levelOrder(TreeNode root){List<List<Integer>> res = new ArrayList<>();Queue<TreeNode> queue = new ArrayDeque<>();if(root != null){queue.add(root);}while (!queue.isEmpty()){int n = queue.size();List<Integer> level = new ArrayList<>();for(int i =0;i<n;i++){TreeNode node = queue.poll();level.add(node.val);if(node.left!=null){queue.add(node.left);}if(node.right!=null){queue.add(node.right);}}res.add(level);}return res;}

二叉树最短路径