当前位置：文江博客文章教程详情

LeetCode 中的关于树的算法

发布于 2023-08-30 20:26:47 字数 31225 浏览 26 评论 0

递归

1.树的高度
2.平衡树
3.两节点的最长路径
4.翻转树
5.归并两棵树
6.判断路径和是否等于一个数
剑指 24.二叉树中和为某一值的路径
7.统计路径和等于一个数的路径数量
8.子树
9.树的对称
10.最小高度
11.统计左叶子节点的和
12.相同节点值的最大路径长度
13.间隔遍历
14.找出二叉树中第二小的节点
15.二叉树的所有路径

层次遍历

剑指 57.二叉树的下一个结点
剑指 59.按之字形打印二叉树
1.一棵树每层节点的平均数
2.得到左下角的节点
3.二叉树的最大宽度
4.判断完全二叉树

前中后序遍历

剑指 57.二叉树的下一个结点
剑指 4.重建二叉树
1.非递归实现前序遍历
2.非递归实现二叉树的后序遍历
3.非递归实现二叉树的中序遍历

BST

剑指 23.二叉搜索树的后序遍历序列
1.修剪二叉查找树
2.寻找二叉查找树的第 k 个元素
3.把二叉查找树每个节点的值都加上比它大的节点的值
4.二叉查找树的最近公共祖先
5.二叉树的最近公共祖先
6.从有序数组中构造二叉查找树
7.根据有序链表构造平衡的二叉查找树
剑指 26.二叉搜索树与双向链表
8.在二叉查找树中寻找两个节点，使它们的和为一个给定值
9.在二叉查找树中查找两个节点之差的最小绝对值
10.寻找二叉查找树中出现次数最多的值

递归

一棵树要么是空树，要么有两个指针，每个指针指向一棵树。树是一种递归结构，很多树的问题可以使用递归来处理。

1.树的高度

104.二叉树的最大深度

class Solution {
  public int maxDepth(TreeNode root) {
    if(root == null) return 0;
    return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
  }
}

2.平衡树

110.给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

思路：当递归需要的返回值和输出不一致时需要创建另外的方法，输出对象放在类中存放最值。

这里需要的输出是真假，而需要的返回值是当前子树的高度。

class Solution {
  private boolean flag = true;
  public boolean isBalanced(TreeNode root) {
    maxDepth(root);
    return flag;
  }
  private int maxDepth(TreeNode root){
    if(root == null) return 0;
    int l = maxDepth(root.left);
    int r = maxDepth(root.right);
    if(Math.abs(l-r) > 1) flag = false;
    return Math.max(l,r) + 1;
  }
}

3.两节点的最长路径

543.给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

Input:

     1
    / \
     2  3
    / \
   4   5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

思路：

直径等于左子树高度加右子树高度。这里需要的输出是最长路径，而递归返回值是当前子树的高度。

class Solution {
  private int max = 0;

  public int diameterOfBinaryTree(TreeNode root) {
    maxDepth(root);
    return max;

  }

  private int maxDepth(TreeNode root){
    if(root == null) return 0;
    int l = maxDepth(root.left);
    int r = maxDepth(root.right);
    max = Math.max(max,l+r);
    return Math.max(l,r) + 1;
  }
}

4.翻转树

226.翻转一棵二叉树。

class Solution {
  public TreeNode invertTree(TreeNode root) {
    if(root == null) return null;
    TreeNode left = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(left);
    return root;
  }
}

5.归并两棵树

617.给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

Input:
     Tree 1           Tree 2
      1             2
     / \             / \
    3   2           1   3
     /               \   \
    5               4   7

Output:
     3
    / \
     4   5
    / \   \
   5   4   7

class Solution {
  public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if(t1 == null && t2 == null) return null;
    if(t1 == null) return t2;
    if(t2 == null) return t1;

    TreeNode root = new TreeNode(t1.val + t2.val);
    root.left = mergeTrees(t1.left,t2.left);
    root.right = mergeTrees(t1.right,t2.right);
    
    return root;
  }
}

6.判断路径和是否等于一个数

112.给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

Given the below binary tree and sum = 22,

        5
       / \
      4   8
       /   / \
      11  13  4
     /  \    \
    7  2    1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

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

    return helper(sequence, start, i-1) && helper(sequence, i, root-1);
  }
}

剑指 24.二叉树中和为某一值的路径

输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

思路：

回溯。

public class Solution {
  ArrayList<ArrayList<Integer>> result = new ArrayList<>();
  ArrayList<Integer> list = new ArrayList<>();
  public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
    if(root == null) return result;
    list.add(root.val);
    if(root.left == null && root.right == null && target == root.val){
      result.add(new ArrayList<Integer>(list));
    }
    FindPath(root.left, target - root.val);
    FindPath(root.right, target - root.val);
    list.remove(list.size()-1);
    return result;
  }
}

7.统计路径和等于一个数的路径数量

437.给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

    10
   /  \
  5   -3
   / \  \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

思路：需要另建方法从根节点开始递归。

class Solution {
  public int pathSum(TreeNode root, int sum) {
    if(root == null) return 0;
    return pathSumFromRoot(root,sum) + pathSum(root.left,sum) + pathSum(root.right,sum);
  }

  private int pathSumFromRoot(TreeNode root, int sum){
    int ret = 0;
    if(root == null) return 0;
    if(sum == root.val) ret++;
    ret += pathSumFromRoot(root.left, sum - root.val) + pathSumFromRoot(root.right, sum - root.val);
    return ret;
  }
}

8.子树

572.给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

Given tree s:
   3
  / \
   4   5
  / \
 1   2

Given tree t:
   4
  / \
 1   2

Return true, because t has the same structure and node values with a subtree of s.

Given tree s:

   3
  / \
   4   5
  / \
 1   2
  /
   0

Given tree t:
   4
  / \
 1   2

Return false.

思路：需要另建方法从根节点开始递归。

class Solution {
  public boolean isSubtree(TreeNode s, TreeNode t) {
    if(s == null) return false;
    return isSubtreeFromRoot(s,t) || isSubtree(s.left,t) || isSubtree(s.right,t);
  }

  public boolean isSubtreeFromRoot(TreeNode s, TreeNode t){
    if(s == null && t == null) return true;
    if(s == null || t == null) return false;
    if(s.val != t.val) return false;
    return isSubtreeFromRoot(s.left, t.left) && isSubtreeFromRoot(s.right, t.right);
  }
}

9.树的对称

101.给定一个二叉树，检查它是否是镜像对称的。

思路：左子树的左子树和右子树的右子树相等且左子树的右子树和右子树的左子树相等。

class Solution {
  public boolean isSymmetric(TreeNode root) {
    if(root == null) return true;
    return isSymmetric(root.left,root.right);
  }

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

10.最小高度

111.给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

思路：叶子节点返回 1，没有左节点则返回右节点的高度+1，没有右节点则返回左节点高度+1，都有返回最小高度＋1，与1.树的高度对比。

class Solution {
  public int minDepth(TreeNode root) {
    if(root == null) return 0;
    int l = minDepth(root.left);
    int r = minDepth(root.right);
    if(l == 0 || r == 0) return l + r + 1;//三种情况均能满足（叶子 j、只有左、只有右）
    return Math.min(l, r) + 1;

  }
}

11.统计左叶子节点的和

404.计算给定二叉树的所有左叶子之和。

  3
   / \
  9  20
  /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

思路：重点是判断是否是叶子节点。

class Solution {
  public int sumOfLeftLeaves(TreeNode root) {
    if(root == null) return 0;
    int left = 0;
    if(isLeaf(root.left)){
      left = root.left.val;
    }
    return left + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
  }

  private boolean isLeaf(TreeNode node){
    if(node == null) return false;
    if(node.left == null && node.right == null) return true;
    return false;
  }
}

12.相同节点值的最大路径长度

687.给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。这条路径可以经过也可以不经过根节点。注意：两个节点之间的路径长度由它们之间的边数表示。

思路：输出最长路径。递归返回值是当前子树的具有相同值的高度。与3.两节点的最长路径相似

class Solution {
  private int max = 0;
  public int longestUnivaluePath(TreeNode root) {
    dfs(root);
    return max;
  }

  private int dfs(TreeNode root){
    if(root == null) return 0;
    int left = dfs(root.left);
    int right = dfs(root.right);
    int leftPath = 0;
    int rightPath = 0;
    if(root.left != null && root.left.val == root.val){
      leftPath = left + 1;
    }
    if(root.right != null && root.right.val == root.val){
      rightPath = right + 1;
    }
    max = Math.max(max, leftPath + rightPath);
    return Math.max(leftPath, rightPath);//这里没加 1，则不是高度，而是路径
  }
}

13.间隔遍历

337.这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

   3
  / \
   2   3
  \   \
   3   1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

思路：动态规划的思想。

对于一个以 node 为根节点的二叉树而言，如果尝试偷取 node 节点，那么势必不能偷取其左右子节点，然后继续尝试偷取其左右子节点的左右子节点。
如果不偷取该节点，那么只能尝试偷取其左右子节点。

比较两种方式的结果，谁大取谁。

  class Solution {
    public int rob(TreeNode root) {
      if(root == null) return 0;
      int val1 = root.val;
      if(root.left != null) val1 += rob(root.left.left) + rob(root.left.right);
      if(root.right != null) val1 += rob(root.right.left) + rob(root.right.right);
      int val2 = rob(root.left) + rob(root.right);
      return Math.max(val1, val2);
    }
  }

14.找出二叉树中第二小的节点

671.给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。

给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。

Input:
   2
  / \
 2   5
  / \
  5  7

Output: 5

思路：如果根节点等于左节点，第二小的值就在左子树上寻找，然后再与右节点比较，如果没找到第二小的值，则右节点是第二小的值；反之亦然。如果均不等于左右节点，则第二小的值不是左节点就是右节点。

class Solution {
  public int findSecondMinimumValue(TreeNode root) {
    if(root == null) return -1;
    if(root.left == null && root.right == null) return -1;
    int left = root.left.val;
    int right = root.right.val;
    if(root.val == left) left = findSecondMinimumValue(root.left);
    if(root.val == right) right = findSecondMinimumValue(root.right);
    if(left != -1 && right != -1) return Math.min(left,right);
    if(left == -1) return right;
    return left;
  }
}

15.二叉树的所有路径

257.给定一个二叉树，返回所有从根节点到叶子节点的路径。

思路：每次都复制 string，不会影响之后的递归。

class Solution {
  private void helper(TreeNode root, String path, List<String> list){
    if(root == null) return;
    path += Integer.toString(root.val);
    if((root.left == null) && (root.right == null)){
      list.add(path.toString());
    }else{
      path += "->";
      helper(root.left, path, list);
      helper(root.right, path, list);
    }
  }
  
  public List<String> binaryTreePaths(TreeNode root) {
    List<String> list = new ArrayList<>();
    helper(root, "", list);
    return list;
  }
}

层次遍历

使用 BFS 进行层次遍历。不需要使用两个队列来分别存储当前层的节点和下一层的节点，因为在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。

剑指 22.从上到下打印二叉树

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

思路：

BFS。

使用队列进行遍历。

public class Solution {
  public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>();
    if(root == null) return result;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    while(!q.isEmpty()){
      TreeNode node = q.poll();
      result.add(node.val);
      if(node.left != null) q.add(node.left);
      if(node.right != null) q.add(node.right);
    }
    return result;
  }
}

剑指 59.按之字形打印二叉树

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

思路：

BFS，使用队列，用一个标志位来决定是否需要翻转。

import java.util.*;
public class Solution {
  public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer> > result = new ArrayList<>();
    if(pRoot == null) return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(pRoot);
    boolean reverse = false;
    while(!queue.isEmpty()){
      ArrayList<Integer> list = new ArrayList<>();
      int size = queue.size();
      for(int i = 0; i < size; i++){
        TreeNode node = queue.poll();
        list.add(node.val);
        if(node.left != null) queue.add(node.left);
        if(node.right != null) queue.add(node.right);
      }
      if(reverse){
        Collections.reverse(list);
      }
      result.add(list);
      reverse = !reverse;
    }
    return result;
  }
}

1.一棵树每层节点的平均数

637.给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.

输入:
  3
   / \
  9  20
  /  \
   15   7
输出: [3, 14.5, 11]
解释:
第 0 层的平均值是 3,  第 1 层是 14.5, 第 2 层是 11. 因此返回 [3, 14.5, 11].

思路：使用一个队列进行 BFS，在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。

class Solution {
  public List<Double> averageOfLevels(TreeNode root) {
    ArrayList<Double> result = new ArrayList<> ();
    if(root == null) return result;
    Queue<TreeNode> q = new LinkedList<> ();
    q.add(root);
    while(!q.isEmpty()){
      int cnt = q.size();
      double sum = 0;
      for(int i = 0; i < cnt; i++){
        TreeNode node = q.poll();
        sum += node.val;
        if(node.left != null) q.add(node.left);
        if(node.right != null) q.add(node.right);
      }
      result.add(sum / cnt);
    }
    return result;
  }
}

2.得到左下角的节点

513.给定一个二叉树，在树的最后一行找到最左边的值。

思路：从右到左 BFS 最后一个就是左下角的节点

class Solution {
  public int findBottomLeftValue(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    TreeNode node = root;
    q.add(root);
    while(!q.isEmpty()){
      node = q.poll();
      if(node.right != null) q.add(node.right);//先右后左
      if(node.left != null) q.add(node.left);
    }
    return node.val;
  }
}

3.二叉树的最大宽度

662.给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的 null 节点也计入长度）之间的长度。

class Solution {
  public int widthOfBinaryTree(TreeNode root) {
    Queue<AnnotatedNode> queue = new LinkedList();
    queue.add(new AnnotatedNode(root, 0, 0));
    int curDepth = 0, left = 0, ans = 0;
    while (!queue.isEmpty()) {
      AnnotatedNode a = queue.poll();
      if (a.node != null) {
        queue.add(new AnnotatedNode(a.node.left, a.depth + 1, a.pos * 2));
        queue.add(new AnnotatedNode(a.node.right, a.depth + 1, a.pos * 2 + 1));
        if (curDepth != a.depth) {
          curDepth = a.depth;
          left = a.pos;
        }
        ans = Math.max(ans, a.pos - left + 1);
      }
    }
    return ans;
  }
}

class AnnotatedNode {
  TreeNode node;
  int depth, pos;
  AnnotatedNode(TreeNode n, int d, int p) {
    node = n;
    depth = d;
    pos = p;
  }
}

4.完全二叉树

958.给定一个二叉树，确定它是否是一个完全二叉树。

百度百科中对完全二叉树的定义如下：

若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。）

思路：

层序遍历判断是否出现过 Null。

class Solution {
  public boolean isCompleteTree(TreeNode root) {
    // 层序遍历
    if (root == null) return true;
    Queue<TreeNode> queue = new LinkedList<>(); 
    queue.add(root);

    boolean flag = false;
    while (!queue.isEmpty()){
      int curCount = queue.size();
      for (int i = 0; i < curCount; i++){
        TreeNode curNode = queue.poll();
        if (curNode != null){
          if (flag) return false;  // 如果在这之前出现过 null 节点，根据完全二叉树的性质，可以判断结果了
          queue.add(curNode.left);
          queue.add(curNode.right);
        }else{ // 记录出现过 null 节点
          flag = true;
        }
      }
    }

    return true;
  }
}

前中后序遍历

层次遍历顺序：[1 2 3 4 5 6]
前序遍历顺序：[1 2 4 5 3 6]
中序遍历顺序：[4 2 5 1 3 6]
后序遍历顺序：[4 5 2 6 3 1]

层次遍历使用 BFS 实现，利用的就是 BFS 一层一层遍历的特性；而前序、中序、后序遍历利用了 DFS 实现。

前序

 void dfs(TreeNode root) {
 	if(root == null) return;
   visit(root);
   dfs(root.left);
   dfs(root.right);
 }

中序

 void dfs(TreeNode root) {
 	if(root == null) return;
   dfs(root.left);
   visit(root);
   dfs(root.right);
 }

后序

 void dfs(TreeNode root) {
 	if(root == null) return;
   dfs(root.left);
   dfs(root.right);
   visit(root);
 }

剑指 57.二叉树的下一个结点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

思路：

中序遍历，寻找。

应先找到根节点。

import java.util.*;
public class Solution {
  List<TreeLinkNode> list = new ArrayList<>();
  public TreeLinkNode GetNext(TreeLinkNode pNode)
  {
    if(pNode == null) return null;
    TreeLinkNode root = pNode;
    while(root.next != null){
      root = root.next;
    }
    inorder(root);
    for(int i = 0; i < list.size()-1; i ++){
      if(list.get(i) == pNode) return list.get(i+1);
    }
    return null;
  }
  private void inorder(TreeLinkNode root){
    if(root == null) return;
    inorder(root.left);
    list.add(root);
    inorder(root.right);
  }
}

剑指 4.重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路：

前序第一个是根节点，中序该值左边是左子树，右边是右子树。

可以用递归继续构建。

import java.util.Arrays;
public class Solution {
  public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    if(pre.length == 0 || in.length == 0) return null;
    TreeNode root = new TreeNode(pre[0]);
    for(int i = 0; i < in.length; i++){
      if(in[i] == pre[0]){
        root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
        root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
        break;
      }
    }
    return root;
  }
}

剑指 61.序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#），以！表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果 str，重构二叉树。

例如，我们可以把一个只有根节点为 1 的二叉树序列化为"1,"，然后通过自己的函数来解析回这个二叉树

public class Solution {
  int index = -1;
  String Serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    if(root == null) return "#,";
    sb.append(root.val).append(",");
    sb.append(Serialize(root.left));
    sb.append(Serialize(root.right));
    return sb.toString();
  }
  TreeNode Deserialize(String str) {
    index++;
    String[] strs = str.split(",");
    if(strs.length <= index) return null;
    if(strs[index].equals("#")) return null;
    TreeNode root = new TreeNode(Integer.valueOf(strs[index]));
    root.left = Deserialize(str);
    root.right = Deserialize(str);
    return root;
  }
}

1.非递归实现前序遍历

144.前序遍历

思路：用栈实现，先访问父节点，再压右再压左

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

2.非递归实现二叉树的后序遍历

145.后序遍历

思路：前序遍历为 root -> left -> right，后序遍历为 left -> right -> root。可以修改前序遍历成为 root -> right -> left，那么这个顺序就和后序遍历正好相反。

class Solution {
  public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if(root == null) return result;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while(!stack.isEmpty()){
      TreeNode node = stack.pop();
      if(node.left != null) stack.push(node.left);
      if(node.right != null) stack.push(node.right);
      result.add(node.val); 
    }
    Collections.reverse(result);
    return result;
  }
}

3.非递归实现二叉树的中序遍历

94.中序遍历

思路：先排着把左节点压入栈，然后从最后一个左节点开始访问，如果该节点有右节点，则开始访问右节点

class Solution {
  public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if(root == null) return result;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while(cur != null || !stack.isEmpty()){
      while(cur != null){
        stack.push(cur);
        cur = cur.left;
      }
      TreeNode node = stack.pop();
      result.add(node.val);
      if(node.right != null){
        cur = node.right;
      }
    }
    return result;
  }
}

BST

二叉查找树（BST）：根节点大于等于左子树所有节点，小于等于右子树所有节点。

二叉查找树中序遍历有序。

剑指 23.二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出 Yes,否则输出 No。假设输入的数组的任意两个数字都互不相同。

思路：最后一个节点为根节点。小于该节点值的为左子树，大于该节点值的为右子树。

public class Solution {
  public boolean VerifySquenceOfBST(int [] sequence) {
    if(sequence.length == 0) return false;
    return helper(sequence, 0, sequence.length-1);
  }
  private boolean helper(int[] sequence, int start, int root){
    if(start >= root) return true;
    int i = start;
    for(; i < root; i++){
      if(sequence[i] > sequence[root]) break;
    }
    for(int j = i; j < root; j++){
      if(sequence[j] < sequence[root]) return false;
    }
    return helper(sequence, start, i-1) && helper(sequence, i, root-1);
  }
}

1. 修剪二叉查找树

669.给定一个二叉搜索树，同时给定最小边界 L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

思路：递归

class Solution {
  public TreeNode trimBST(TreeNode root, int L, int R) {
    if(root == null) return null;
    if(root.val > R) return trimBST(root.left, L, R);
    if(root.val < L) return trimBST(root.right, L, R);
    root.left = trimBST(root.left, L, R);
    root.right = trimBST(root.right, L, R);
    return root;


  }
}

2. 寻找二叉查找树的第 k 个元素

230.给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？

输入: root = [5,3,6,2,4,null,null,1], k = 3
     5
    / \
   3   6
  / \
   2   4
  /
 1
输出: 3

思路：中序遍历，避免用数组储存

class Solution {

  int cnt = 0;
  int val;

  public int kthSmallest(TreeNode root, int k) {
    inOrder(root, k);
    return val;
  }

  void inOrder(TreeNode root, int k) {
    if(root == null) return;
    inOrder(root.left, k);
    cnt++;
    if(cnt == k){
      val = root.val;
    }
    inOrder(root.right, k);
  }
}

3. 把二叉查找树每个节点的值都加上比它大的节点的值

538.给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

输入: 原始二叉搜索树:
        5
      /   \
       2   13

输出: 转换为累加树:
       18
      /   \
      20   13

思路：倒着的中序遍历

class Solution {

  int sum = 0;
  public TreeNode convertBST(TreeNode root) {
    if(root == null) return null;
    convertBST(root.right);
    root.val += sum;
    sum = root.val;
    convertBST(root.left);
    return root;
  }
}

4. 二叉查找树的最近公共祖先

235.给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路：利用 BST 的特性，p<=x<=q 是最近公共祖先的充分必要条件

class Solution {
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
    if(root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
    return root;
  }
}

5. 二叉树的最近公共祖先

236。

思路：通过递归对二叉树进行后序遍历，当遇到节点 ppp 或 qqq 时返回。从底至顶回溯，当节点 p,qp, qp,q 在节点 rootrootroot 的异侧时，节点 rootrootroot 即为最近公共祖先，则向上返回 rootrootroot 。

class Solution {
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if(left == null) return right;
    if(right == null) return left;
    return root;

  }
}

6. 从有序数组中构造二叉查找树

108.将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

    0
   / \
   -3   9
   /   /
 -10  5

思路：高度平衡意味着每次必须选择中间数字作为根节点。

class Solution {

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

  public TreeNode sortedArrayToBST(int[] nums) {
    return helper(0,nums.length-1,nums);
  }
}

7. 根据有序链表构造平衡的二叉查找树

109.给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

思路：使用快慢指针寻找中间值（需要找到中间节点的前一个节点）

class Solution {
  public TreeNode sortedListToBST(ListNode head) {
    //有下面两种边界问题
    if(head == null) return null;
    if(head.next == null) return new TreeNode(head.val);
    ListNode preMid = helper(head);
    ListNode mid = preMid.next;
    preMid.next = null;//从这里断开链表
    TreeNode root = new TreeNode(mid.val);
    root.left = sortedListToBST(head);
    root.right = sortedListToBST(mid.next);
    return root;
  }


  //寻找 preMid
  ListNode helper(ListNode head){
    ListNode slow = head;
    ListNode fast = head.next.next;
    while(fast != null && fast.next != null){
      slow = slow.next;
      fast = fast.next.next;
    }
    return slow;
  }
}

剑指 26.二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

思路：线索化二叉树。类似于中序遍历构建。由于正向构建时，指针会移动到尾部，因此反向构建。

public class Solution {
  TreeNode pre = null;
  public TreeNode Convert(TreeNode pRootOfTree) {
    if(pRootOfTree == null) return null;
    Convert(pRootOfTree.right);
    if(pre!=null){
      pRootOfTree.right = pre;
      pre.left = pRootOfTree;
    }
    pre = pRootOfTree;
    Convert(pRootOfTree.left);
    return pre;
  }
}

8. 在二叉查找树中寻找两个节点，使它们的和为一个给定值

653.给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

输入: 
  5
   / \
  3   6
 / \   \
2   4   7

Target = 9

输出: True

使用中序遍历得到有序数组之后，再利用双指针对数组进行查找。

class Solution {
  public boolean findTarget(TreeNode root, int k) {
    List<Integer> inOrder = new ArrayList<>();
    inOrder(root, inOrder);
    int left = 0, right = inOrder.size() - 1;
    while(left < right){
      int sum = inOrder.get(left) + inOrder.get(right);
      if(sum == k) return true;
      else if(sum > k) right--;
      else left ++;
    }
    return false;
  }

  void inOrder(TreeNode root, List<Integer> inOrder){
    if(root == null) return;
    inOrder(root.left, inOrder);
    inOrder.add(root.val);
    inOrder(root.right, inOrder);
  }
}

9. 在二叉查找树中查找两个节点之差的最小绝对值

530.给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

思路：通过中序遍历寻找

class Solution {

  int min = Integer.MAX_VALUE;//存储最小值
  TreeNode preNode = null;//存储前一个结点

  public int getMinimumDifference(TreeNode root) {
    inOrder(root);
    return min;
  }

  void inOrder(TreeNode root){
    if(root == null) return;
    inOrder(root.left);
    int cur = root.val;
    if(preNode != null)
      //后一个节点肯定大于前一个节点
      min = Math.min(cur - preNode.val, min);
    preNode = root;
    inOrder(root.right);
  }
}

10. 寻找二叉查找树中出现次数最多的值

501.给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

如果众数超过 1 个，不需考虑输出顺序。

你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

思路：毫无疑问，同样使用中序遍历。

class Solution {

  TreeNode pre = null;
  int curCnt = 0;
  int maxCnt = 0;

  public int[] findMode(TreeNode root) {
    List<Integer> nums = new ArrayList<>();
    inOrder(root,nums);
    int[] result = new int[nums.size()];
    for(int i = 0; i < nums.size(); i++){
      result[i] = nums.get(i);
    }
    return result;
  }

  void inOrder(TreeNode root, List<Integer> nums){
    if(root == null) return;
    inOrder(root.left, nums);
    int cur = root.val;
    if(pre != null)
      curCnt = cur == pre.val ?(curCnt + 1) : 0;
    if(curCnt == maxCnt){
      nums.add(cur);
    }
    if(curCnt > maxCnt){
      maxCnt = curCnt;
      nums.clear();
      nums.add(cur);
    }
    pre = root;
    inOrder(root.right, nums);
  }
}

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

列表为空，暂无数据

关于作者

泪冰清

暂无简介

0 文章

0 评论

700 人气

关注发私信

友情链接

文江博客

LeetCode 中的关于 树 的算法

递归

层次遍历

前中后序遍历

BST

递归

1.树的高度

2.平衡树

3.两节点的最长路径

4.翻转树

5.归并两棵树

6.判断路径和是否等于一个数

剑指 24.二叉树中和为某一值的路径

7.统计路径和等于一个数的路径数量

8.子树

9.树的对称

10.最小高度

11.统计左叶子节点的和

12.相同节点值的最大路径长度

13.间隔遍历

14.找出二叉树中第二小的节点

15.二叉树的所有路径

层次遍历

剑指 22.从上到下打印二叉树

剑指 59.按之字形打印二叉树

1.一棵树每层节点的平均数

2.得到左下角的节点

3.二叉树的最大宽度

4.完全二叉树

前中后序遍历

剑指 57.二叉树的下一个结点

剑指 4.重建二叉树

剑指 61.序列化二叉树

1.非递归实现前序遍历

2.非递归实现二叉树的后序遍历

3.非递归实现二叉树的中序遍历

BST

剑指 23.二叉搜索树的后序遍历序列

1. 修剪二叉查找树

2. 寻找二叉查找树的第 k 个元素

3. 把二叉查找树每个节点的值都加上比它大的节点的值

4. 二叉查找树的最近公共祖先

5. 二叉树的最近公共祖先

6. 从有序数组中构造二叉查找树

7. 根据有序链表构造平衡的二叉查找树

剑指 26.二叉搜索树与双向链表

8. 在二叉查找树中寻找两个节点，使它们的和为一个给定值

9. 在二叉查找树中查找两个节点之差的最小绝对值

10. 寻找二叉查找树中出现次数最多的值

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

你可能也喜欢

发布评论

关于作者

热门标签

推荐作者

友情链接

LeetCode 中的关于树的算法

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。