AI 助理
备案控制台
开发者社区 人工智能 文章 正文

常见的二叉树系统题解（一）

2024-01-11 71
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 常见的二叉树系统题解（一）

LeetCode 树的定义

二叉树

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

N叉树

public class Node {
    public int val;
    public List<Node> children;
    public Node() {
    }
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}

二叉树遍历

二叉树最基本的遍历方式就是：前序遍历、中序遍历和后序遍历。

  • 前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。
  • 中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。
  • 后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。

简单概况如下：

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

TIPS：前中后序遍历区别在于三字中的中间那个字，前、中、后序分别对应左、根、右。

二叉树前序遍历

  1. 二叉树的前序遍历

给定一个二叉树，返回它的 前序 遍历。

示例:

输入: [1,null,2,3]  
       1
        \
         2
        /
       3 
    输出: [1,2,3]
`进阶`: 递归算法很简单，你可以通过迭代算法完成吗？

递归

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    robot(root, ans);
    return ans;
}
private void robot(TreeNode p, List<Integer> ans) {
    if(p == null) return;
    // 根左右
    ans.add(p.val);
    robot(p.left, ans);
    robot(p.right, ans);
}

迭代

迭代步骤：

  1. 从根节点开始，每次迭代弹出当前栈顶元素
  2. 将其孩子节点压入栈中（先压右孩子再压左孩子）
public List<Integer> preorderTraversal2(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    // 将根节点入栈
    stack.push(root);
    while (!stack.isEmpty()) {
        // 取出栈顶元素
        TreeNode tmp = stack.pop();
        if (tmp != null) {
            ans.add(tmp.val);
            // 将其孩子节点压入栈中（先右节点、再左节点）
            stack.add(tmp.right);
            stack.add(tmp.left);
        }
    }
    return ans;
}

算法复杂度:

  • 时间复杂度：树中每个节点都遍历一次，因此时间复杂度为 O(N)，其中 N 为树中节点的数量。
  • 空间复杂度：
  • 最坏情况：树为链表，树的高度=树的节点个数，此时空间复杂度是 O(N)。
  • 最好情况：树高度平衡，此时空间复杂度是 O(logn)。

二叉树中序遍历

  1. 二叉树的中序遍历

给定一个二叉树，返回它的 中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3
输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

递归

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    robot(root, ans);
    return ans;
}
private void robot(TreeNode root, List<Integer> ans) {
    if (root == null) {
        return;
    }
    // 左根右
    robot(root.left, ans);
    ans.add(root.val);
    robot(root.right, ans);
}

迭代

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    while (!stack.isEmpty() || root != null) {
        // 一直放入左儿子（左）
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        // 访问当前元素（根），把右儿子入栈（右）
        if (!stack.isEmpty()) {
            root = stack.pop();
            ans.add(root.val);
            root = root.right;
        }
    }
    return ans;
}

算法复杂度

  • 时间复杂度：O(n)。递归函数 T(n) = 2⋅T(n/2)+1。
  • 空间复杂度：最坏情况下需要空间O(n)，平均情况为O(logn)。

二叉树后序遍历

  1. 二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 
输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

递归

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    robot(root, ans);
    return ans;
}
private void robot(TreeNode p, List<Integer> ans) {
    if (p == null) {
        return;
    }
    // 左右根
    robot(p.left, ans);
    robot(p.right, ans);
    ans.add(p.val);
}

后序遍历的非递归写法有些麻烦，因为节点第一次访问时并不打印，而是在第二次遍历时才打印。所以需要一个变量来标记该结点是否访问过。

迭代：利用辅助类

public class StackNode {
    TreeNode root;
    boolean visit;
    StackNode(TreeNode root) {
        this.root = root;
    }
}
public List<Integer> postorderTraversal2(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    Stack<StackNode> stack = new Stack<>();
    StackNode node;
    stack.push(new StackNode(root));
    while (!stack.isEmpty()) {
        node = stack.pop();
        if (node == null) {
            continue;
        }
        if (!node.visit) {
            node.visit = true;
            stack.push(node);
            if (node.root.right != null) {
                stack.push(new StackNode(node.root.right));
            }
            if (node.root.left != null) {
                stack.push(new StackNode(node.root.left));
            }
        } else if (node.root != null) {
            ans.add(node.root.val);
        }
    }
    return ans;
}

迭代：逆序输出

public List<Integer> postorderTraversal3(TreeNode root) {
    LinkedList<Integer> ans = new LinkedList<>();
    if (root == null) {
        return ans;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        ans.addFirst(node.val);
        if (node.left != null) {
            stack.push(node.left);
        }
        if (node.right != null) {
            stack.push(node.right);
        }
    }
    return ans;
}

算法复杂度：

  • 时间复杂度：访问每个节点恰好一次，因此时间复杂度为 O(N)，其中 N 是节点的个数，也就是树的大小。
  • 空间复杂度：取决于树的结构，最坏情况需要保存整棵树，因此空间复杂度为 O(N)。

二叉树的层次遍历

  1. 二叉树的层次遍历

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如：给定二叉树: [3,9,20,null,null,15,7],

3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

递归

首先确认树非空，然后调用递归函数 helper(node, level)，参数是当前节点和节点的层次。

算法过程:

  1. ans 为结果列表，level 为当前遍历的层数（初始为0）
  2. 若 ans 的长度 = level，向 ans 增加一个空列表
  3. 将节点值放入 ans 的第 level 个列表结尾
  4. 遍历左右子节点，此时 level + 1
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    robot(root, ans, 0);
    return ans;
}
private void robot(TreeNode root, List<List<Integer>> ans, int level) {
    if (root == null) {
        return;
    }
    if (ans.size() == level) {
        ans.add(new ArrayList());
    }
    ans.get(level).add(root.val);
    robot(root.left, ans, level + 1);
    robot(root.right, ans, level + 1);
}

复杂度分析

  • 时间复杂度：O(N)，因为每个节点恰好会被运算一次。
  • 空间复杂度：O(N)，保存输出结果的数组包含 N 个节点的值。

迭代

算法过程：

第 0 层只包含根节点 root ，算法实现如下：

  1. 初始化队列只包含一个节点 root 和层次编号 0 ： level = 0。
  2. 当队列非空的时候：
  • 新建一个空列表，表示当前层结果 current。
  • 计算当前层有多少个元素：等于队列的长度。
  • 将这些元素从队列中弹出，并加入 current 列表中。
  • 将他们的孩子节点作为下一层压入队列中。
  • 将 当前层结果 current 放入 ans 中。
  • 进入下一层循环。
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        List<Integer> current = new ArrayList<>();
        // 当前层的元素个数
        int length = queue.size();
        for (int i = 0; i < length; ++i) {
            TreeNode node = queue.remove();
            // 放入结果
            current.add(node.val);
            // 依次将 node 的左右子节点加入队列
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        ans.add(current);
    }
    return ans;
}

复杂度分析

  • 时间复杂度：O(N)，因为每个节点恰好会被运算一次。
  • 空间复杂度：O(N)，保存输出结果的数组包含 N 个节点的值。

二叉树的右视图

  1. 二叉树的右视图

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

本题是层序遍历的变种，层序遍历是存储二叉树每行的每个元素，而本题仅存储二叉树每行的最后一个元素。

递归

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    robot(root, ans, 0);
    return ans;
}
private void robot(TreeNode root, List<Integer> ans, int level) {
    if (root == null) {
        return;
    }
    if (ans.size() == level) {
        ans.add(root.val);
    }
    // 层序遍历的 ans 是一个 List<List<Integer>，是 ans.get(level).add(root.val);
    ans.set(level, root.val);
    robot(root.left, ans, level + 1);
    robot(root.right, ans, level + 1);
}

迭代

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int current = 0;
        // 当前层的元素个数
        int length = queue.size();
        for (int i = 0; i < length; ++i) {
            TreeNode node = queue.remove();
            // 放入结果
            current = node.val;
            // 依次将 node 的左右子节点加入队列
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        ans.add(current);
    }
    return ans;
}

在每个树行中找最大值

  1. 在每个树行中找最大值

您需要在二叉树的每一行中找到最大的值。

示例：

输入:

1
     / \
    3   2
   / \   \  
  5   3   9 
输出: [1, 3, 9]

本题也是层序遍历的变种，层序遍历是存储二叉树每行的每个元素，而本题仅存储二叉树每行的最大元素。

递归

public List<Integer> largestValues(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    robot(root, ans, 0);
    return ans;
}
private void robot(TreeNode root, List<Integer> ans, int level) {
    if (root == null) {
        return;
    }
    if (ans.size() <= level) {
        ans.add(Integer.MIN_VALUE);
    }
    ans.set(level, Math.max(ans.get(level), root.val));
    robot(root.left, ans, level + 1);
    robot(root.right, ans, level + 1);
}

迭代

public List<Integer> largestValues(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int current = Integer.MIN_VALUE;
        // 当前层的元素个数
        int length = queue.size();
        for (int i = 0; i < length; ++i) {
            TreeNode node = queue.remove();
            // 放入结果（变化的地方）
            current = Math.max(current, node.val);
            // 依次将 node 的左右子节点加入队列
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        ans.add(current);
    }
    return ans;
}

二叉树的垂序遍历

  1. 二叉树的垂序遍历

给定二叉树，按垂序遍历返回其结点值。

对位于 (X, Y) 的每个结点而言，其左右子结点分别位于 (X-1, Y-1) 和 (X+1, Y-1)。

把一条垂线从 X = -infinity 移动到 X = +infinity ，每当该垂线与结点接触时，我们按从上到下的顺序报告结点的值（ Y 坐标递减）。

如果两个结点位置相同，则首先报告的结点值较小。

按 X 坐标顺序返回非空报告的列表。每个报告都有一个结点值列表。

示例 1：

输入：[3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]
解释： 
在不丧失其普遍性的情况下，我们可以假设根结点位于 (0, 0)：
然后，值为 9 的结点出现在 (-1, -1)；
值为 3 和 15 的两个结点分别出现在 (0, 0) 和 (0, -2)；
值为 20 的结点出现在 (1, -1)；
值为 7 的结点出现在 (2, -2)。

示例 2：

输入：[1,2,3,4,5,6,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
根据给定的方案，值为 5 和 6 的两个结点出现在同一位置。
然而，在报告 "[1,5,6]" 中，结点值 5 排在前面，因为 5 小于 6。

提示：

树的结点数介于 1 和 1000 之间。

每个结点值介于 0 和 1000 之间。

解题思路

设根节点的(x,y)=(0,0)，对于节点坐标(x,y)，其左节点坐标为(x-1,y-1)，右节点坐标为(x+1,y-1)。

  1. 构造 List posNodes，遍历二叉树每个节点，填入 PositionNode 的 x 坐标、y 坐标、val 值。
  2. 将 posNodes 展开成 key 是 x 坐标、value 是对应 PositionNode 的 positionMap，注意这里使用 TreeMap，因为要对 x 坐标排序。
  3. 构建结果 ans：遍历 positionMap，相同位置节点，按照自然顺序排序（即先按照 Y 降序排列；若 Y 相同，则按照 val 升序排列）

代码

public class PositionNode {
    int val;
    int x;
    int y;
    PositionNode(int val, int x, int y) {
        this.val = val;
        this.x = x;
        this.y = y;
    }
    public int getVal() {
        return val;
    }
    public int getX() {
        return x;
    }
    public int getY() {
        return y;
    }
}
public List<List<Integer>> verticalTraversal(TreeNode root) {
    // 构建节点的位置信息
    List<PositionNode> posNodes = new ArrayList<>();
    robot(root, posNodes, 0, 0);
    // 将 posNodes 展开成 key 是 x 坐标、value 是对应 PositionNode 的 map
    // 注意这里使用 TreeMap，因为要对 x 坐标排序
    Map<Integer, List<PositionNode>> positionMap = posNodes.stream().collect(
            Collectors.groupingBy(PositionNode::getX, TreeMap::new, Collectors.toList()));
    // 构建结果
    List<List<Integer>> ans = new ArrayList<>();
    positionMap.forEach((k, v) -> {
        // 题目要求：相同位置节点，按照自然顺序排序（即先按照 Y 降序排列；若 Y 相同，则按照 val 升序排列）
        v.sort(Comparator.comparing(PositionNode::getY).reversed()
                .thenComparing(PositionNode::getVal));
        ans.add(v.stream().map(PositionNode::getVal).collect(Collectors.toList()));
    });
    return ans;
}
private void robot(TreeNode root, List<PositionNode> posNodes, int x, int y) {
    if (root == null) {
        return;
    }
    posNodes.add(new PositionNode(root.val, x, y));
    // 根节点的(x,y)=(0,0)，若某个节点坐标为(x,y)，则左节点坐标为(x-1,y-1)，右节点坐标为(x+1,y-1)
    robot(root.left, posNodes, x - 1, y - 1);
    robot(root.right, posNodes, x + 1, y - 1);

二叉树的锯齿形层次遍历

  1. 二叉树的锯齿形层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：

给定二叉树 [3,9,20,null,null,15,7],

3
   / \
  9  20
    /  \
   15   7

返回锯齿形层次遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

本题是层序遍历的变种，仅需将层序遍历的偶数行逆序即可。

递归

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    robot(root, ans, 0);
    // 与层序遍历相比，变化的部分
    for (int i = 1; i < ans.size(); i += 2) {
        Collections.reverse(ans.get(i));
    }
    return ans;
}
private void robot(TreeNode root, List<List<Integer>> ans, int level) {
    if (root == null) {
        return;
    }
    if (ans.size() == level) {
        ans.add(new ArrayList());
    }
    ans.get(level).add(root.val);
    robot(root.left, ans, level + 1);
    robot(root.right, ans, level + 1);
}

迭代

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        List<Integer> current = new ArrayList<>();
        // 当前层的元素个数
        int length = queue.size();
        for (int i = 0; i < length; ++i) {
            TreeNode node = queue.remove();
            // 放入结果
            current.add(node.val);
            // 依次将 node 的左右子节点加入队列
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        ans.add(current);
    }
    // 与层序遍历相比，变化的部分
    for (int i = 1; i < ans.size(); i += 2) {
        Collections.reverse(ans.get(i));
    }
    return ans;
}

N 叉树遍历

N叉树的层序遍历

  1. N叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

例如，给定一个 3叉树 :

返回其层序遍历:

[
     [1],
     [3,2,4],
     [5,6]
]

说明:

  1. 树的深度不会超过 1000。
  2. 树的节点总数不会超过 5000。
public List<List<Integer>> levelOrder(Node root) {
    List<List<Integer>> ans = new ArrayList<>();
    robot(root, ans, 0);
    return ans;
}
private void robot(Node root, List<List<Integer>> ans, int level) {
    if (root == null) {
        return;
    }
    if (ans.size() <= level) {
        ans.add(new ArrayList<>());
    }
    ans.get(level).add(root.val);
    if (root.children == null) {
        return;
    }
    for (Node child : root.children) {
        robot(child, ans, level + 1);
    }
}

N叉树的前序遍历

  1. N叉树的前序遍历

给定一个 N 叉树，返回其节点值的前序遍历。

例如，给定一个 3叉树 :

返回其前序遍历: [1,3,5,6,2,4]。

说明: 递归法很简单，你可以使用迭代法完成此题吗？

递归
public List<Integer> preorder(Node root) {
    List<Integer> ans = new ArrayList<>();
    robot(root, ans);
    return ans;
}
private void robot(Node root, List<Integer> ans) {
    if (root == null) {
        return;
    }
    ans.add(root.val);
    if (root.children == null) {
        return;
    }
    for (Node child : root.children) {
        robot(child, ans);
    }
}
迭代
public List<Integer> preorder(Node root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    Deque<Node> deque = new ArrayDeque<>();
    deque.push(root);
    while (!deque.isEmpty()) {
        Node tmp = deque.pop();
        if (tmp != null) {
            ans.add(tmp.val);
            if (tmp.children == null) {
                continue;
            }
            for (int i = tmp.children.size() - 1; i >= 0; i--) {
                deque.push(tmp.children.get(i));
            }
        }
    }
    return ans;
}

N叉树的后序遍历

  1. N叉树的后序遍历

给定一个 N 叉树，返回其节点值的后序遍历。

例如，给定一个 3叉树 :

返回其后序遍历: [5,6,3,2,4,1].

说明: 递归法很简单，你可以使用迭代法完成此题吗?

递归
public List<Integer> postorder(Node root) {
    List<Integer> ans = new ArrayList<>();
    robot(root, ans);
    return ans;
}
private void robot(Node root, List<Integer> ans) {
    if (root == null) {
        return;
    }
    if (root.children != null) {
        for (Node child : root.children) {
            robot(child, ans);
        }
    }
    ans.add(root.val);
}
迭代
// 后续遍历：左右中
// 迭代顺序：中右左
public List<Integer> postorder(Node root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Node pop = stack.pop();
        ans.add(pop.val);
        List<Node> children = pop.children;
        if (children == null) {
            continue;
        }
        for (Node child : children) {
            stack.push(child);
        }
    }
    Collections.reverse(ans);
    return ans;
}

二叉搜索树

不同的二叉搜索树

  1. 不同的二叉搜索树

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
public int numTrees(int n) {
    int[] ans = new int[n + 2];
    ans[0] = 1; ans[1] = 1; ans[2] = 2;
    // f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ……
    for(int i = 3; i <= n; i++) {
        for(int j = 0; j <= i - 1; j++) {
            ans[i] += ans[j] * ans[i - j - 1];
        }
    }
    return ans[n];
}

不同的二叉搜索树 II

  1. 不同的二叉搜索树 II

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

示例:

输入: 3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：
   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
public List<TreeNode> generateTrees(int n) {
    if(n <= 0) return new ArrayList<>();
    return build(1, n);
}
private List<TreeNode> build(int start, int end) {
    List<TreeNode> roots = new ArrayList<>();       
    if(start > end) {           
        // null也要放入，否则下面的双重循环进不去
        roots.add(null);
        return roots;
    }
    if(start == end) {
        roots.add(new TreeNode(start));
        return roots;
    }
    for(int i = start; i <= end; i++) {
        List<TreeNode> leftList = build(start, i - 1);
        List<TreeNode> rightList = build(i + 1, end);
        for(TreeNode left : leftList) {             
            for(TreeNode right : rightList) {
                TreeNode root = new TreeNode(i);
                root.left = left;
                root.right = right;
                roots.add(root);
            }
        }
    }
    return roots;
}

验证二叉搜索树

  1. 验证二叉搜索树

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

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

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

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。
public boolean isValidBST(TreeNode root) {
    // 用long型
    return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean isValidBST(TreeNode root, long min, long max) {
    if (root == null) {
        return true;
    }
    if (root.val >= max || root.val <= min) {
        return false;
    }
    return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
}

恢复二叉搜索树

  1. 恢复二叉搜索树

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

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

示例 1:

输入: [1,3,null,null,2]
   1
  /
 3
  \
   2
输出: [3,1,null,null,2]
   3
  /
 1
  \
   2

示例 2:

输入: [3,1,4,null,null,2]
  3
 / \
1   4
   /
  2
输出: [2,1,4,null,null,3]
  2
 / \
1   4
   /
  3

进阶:

  • 使用 O(n) 空间复杂度的解法很容易实现。
  • 你能想出一个只使用常数空间的解决方案吗？
TreeNode first = null, second = null;
TreeNode pre = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
    if(root == null) return;
    robot(root);
    if(first != null && second != null) {
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }
}
private void robot(TreeNode root) {
    if(root == null) return;
    robot(root.left);
    // 找到交换的两个节点
    if(first == null && pre.val > root.val) {
        first = pre;
    }
    if(first != null && pre.val > root.val) {
        second = root;
    }
    pre = root;
    robot(root.right);
}

常见的二叉树系统题解（二）：https://developer.aliyun.com/article/1416668

文章标签：
算法
存储
鱼找水需要时间
目录
相关文章
GR鲸鱼
|
6月前
|
存储 算法 IDE
数据结构与算法⑯(第四章_下)二叉树的层序遍历+判断完全二叉树+一道OJ
数据结构与算法⑯(第四章_下)二叉树的层序遍历+判断完全二叉树+一道OJ
GR鲸鱼
50 1
过。
|
6月前
|
存储
二叉树常见题目
二叉树常见题目
过。
31 0
qiuqiushuibx
|
算法
代码随想录 Day11 二叉树 LeetCode T144,145,94 前中后序遍历 (递归解法)
代码随想录 Day11 二叉树 LeetCode T144,145,94 前中后序遍历 (递归解法)
qiuqiushuibx
47 0
~小白学编程~
|
存储 C++
【C++】二叉搜索树经典OJ题目
二叉搜索树的几道经典OJ面试题
~小白学编程~
75 0
鱼找水需要时间
|
6月前
|
存储 算法
常见的二叉树系统题解（二）
常见的二叉树系统题解（二）
鱼找水需要时间
81 5
唐唐思
|
6月前
二叉树OJ题目（2）
二叉树OJ题目（2）
唐唐思
31 0
dbln
|
6月前
二叉树基础OJ题
二叉树基础OJ题
dbln
35 1
Hsu琛君珩
|
算法
代码随想录算法训练营第十四天 | LeetCode 102. 二叉树的层序遍历、LeetCode 226. 翻转二叉树、LeetCode 101. 对称二叉树
代码随想录算法训练营第十四天 | LeetCode 102. 二叉树的层序遍历、LeetCode 226. 翻转二叉树、LeetCode 101. 对称二叉树
Hsu琛君珩
55 0
Hsu琛君珩
|
存储 算法
代码随想录算法训练营第十三天 | LeetCode 144. 二叉树的前序遍历、LeetCode 145. 二叉树的后序遍历、LeetCode 94. 二叉树的中序遍历
代码随想录算法训练营第十三天 | LeetCode 144. 二叉树的前序遍历、LeetCode 145. 二叉树的后序遍历、LeetCode 94. 二叉树的中序遍历
Hsu琛君珩
59 0
小沈熬夜秃头中
力扣---二叉树OJ题(多种题型二叉树)
第十三弹——力扣LeetCode每日一题
小沈熬夜秃头中
92 0
力扣---二叉树OJ题(多种题型二叉树)