二叉树

分手后的思念是犯贱 2021-08-30 12:51 371阅读 0赞

### 二叉树 ###

*  1. 树（Tree）的基本概念
 *  2. 有序树、无序树和森林
 *  3. 二叉树
 *  4. 二叉树的性质
 *  5. 真二叉树
 *  6. 满二叉树
 *  7. 完全二叉树
 *  8. 完全二叉树的性质
 *   *  测试题
 *  9. 构建二叉树
 *  10. 二叉树的遍历
 *   *  前序遍历
     *  中序遍历
     *  后序遍历
     *  层序遍历
 *  11. 遍历的应用
 *   *  树状打印二叉树
     *  计算二叉树的高度
     *  判断一棵树是否为完全二叉树
     *  翻转二叉树
     *  重建二叉树
     *  前驱节点
     *  后继节点

# 1. 树（Tree）的基本概念 #

树(`Tree`)是`n`(`n≧0`)个结点的有限集。在任意一颗非空树中：有且仅有一个特定的称为根的结点。`n=0`时称为空树。

`n=0`时称为空树。

`n>1`时，其余结点可分为`m`(`m>0`)个互不相交的有限集`T1`，`T2`，`T3`，……，`Tm`，其中每个集合本身又是一棵树，并且称为根的子树。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70]

*  **节点**：树中的每一个元素都是一个节点，如上图中`1`，`2`，`3`，`4`，`5`，`6`等都是树的节点，节点可以为`NULL`，上图中并未直接画出。
 *  **根节点**：一棵树中有且仅有一个根节点，上图中`1`为根节点。
 *  **父节点**：上图中`1`是`2`、`3`、`4`的父节点，`2`是`4`和`5`的父节点…。
 *  **子节点**：上图中`2`、`3`和`4`分别是`1`的子节点…。
 *  **兄弟节点**：父节点的子节点被称为兄弟节点，如`4`和`5`之间为兄弟节点。
 *  **节点的度（degree）**：子树的个数，如节点`1`的度为`3`，节点`2`的度为`2`。
 *  **树的度（degree）**：所有节点度中最大的值。
 *  **叶子节点（leaf）**：度为 `0` 的节点。
 *  **非叶子节点**：度不为`0`的节点。
 *  **层数**：根节点在第一层，根节点的子节点在第二层，以此类推。
 *  **节点的深度（depth）**：从根节点到当前节点的唯一路径的节点总数，如节点`4`的深度为`3`。
 *  **节点的高度（height）**：从当前节点到最远叶子节点的路径上的节点总数，如节点`4`的高度为`2`。
 *  **树的深度**：所有节点深度中的最大值。
 *  **树的高度**：所有节点高度中的最大值。
 *  **树的深度等于树的高度**。

# 2. 有序树、无序树和森林 #

*  有序树

树中任意节点的子节点之间有顺序关系

*  无序树

树中任意节点的子节点之间没有顺序关系

也称为”自由树”

*  森林

由`m` (`m≥0`)棵互不相交的树组成的集合

# 3. 二叉树 #

*  二叉树的特点

每个节点的度最大为`2` （最多拥有`2`棵子树）。

左子树和右子树是有顺序的。

即使某节点只有一棵子树，也要区分左右子树。

*  二叉树是有序树还是无序树？

有序树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 1]

# 4. 二叉树的性质 #

1.  非空二叉树的第`i`层最多有`2^(i-1)`个节点。
2.  在高度为`h`的二叉树上最多有`2^h - 1`个结点（`h≥1`）
3.  对于任何一棵非空二叉树，如果叶子节点个数为`n0`，度为`2`的节点个数为`n2`，则有：`n0 = n2 + 1`。

假设度为`1`的节点的个数为`n1`，则有`no + n1 + n2 = n`，`n`为节点的个数。当节点个数为`n`时，则二叉树中边的个数为`n-1`。当度为`2`的节点个数为`n2`，则存在的边数为`2 * n2`，当度为`1`的节点个数为`n1`，则存在的边数为`n1`，当度为`0`的节点个数为`n0`，则存在的边数为`0`，可得`2 * n2 + n1 = n - 1`。

# 5. 真二叉树 #

*  真二叉树：所有节点的度都要么为`0`，要么为`2`。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 2]

# 6. 满二叉树 #

*  满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 3]

*  在同样高度的二叉树中，满二叉树的叶子节点数量最多、总节点数量最多。
 *  满二叉树一定是真二叉树，真二叉树不一定是满二叉树。
 *  假设满二叉树的高度为`h` （`h≥1`），那么

第`i`层的节点数量:`2^(i-1)`。

叶子节点数量: `2^(h-1)`。

总节点的数量`n`，`n = 2 ^ h- 1 = 2 ^ 0 + 2 ^ 1 + ...... + 2 ^ (h-1)`，则`h = log(n + 1)`。

# 7. 完全二叉树 #

*  完全二叉树：叶子节点只会出现最后`2`层，且最后`1`层的叶子结点都靠左对齐。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 4]

*  完全二叉树从根结点至倒数第`2`层是一棵满二叉树
 *  满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

# 8. 完全二叉树的性质 #

*  度为`1`的节点只有左子树。
 *  度为`1`的节点要么是`1`个，要么是`0`个。
 *  同样节点数量的二叉树，完全二叉树的高度最小。
 *  假设完全二叉树的高度为`h`(`h≥1`)，那么
    
     *  至少有`2^(h-1)`个节点( `2^0 + 2^1 +2^2 + ... + 2^(h-2) +1`)
     *  最多有`2^h - 1`个节点(`2^0 + 2^1 + 2^2 + ... + 2^(h-1)`， 满二叉树)
     *  总节点数量为`n`
        
         *  `2^(h-1) <= n < 2^h`
         *  `h - 1 <= log(n) < h`
         *  `h = floor(log(n)) + 1`
 *  一棵有`n`个节点的完全二叉树(`n>0`)，从上到下、从左到右对节点从`0`开始进行编号,对任意第`i`个节点。
    
     *  如果`i = 0`,它是根节点。
     *  如果`i > 0`，它的父节点编号为`floor(i-1)/2)`。
     *  如果`2i + 1 ≤ n -1`,它的左子节点编号为`2i + 1`。
     *  如果`2i + 1 > n-1`，它无左子节点。
     *  如果`2i + 2 ≤ n-1`，它的右子节点编号为`2i+ 2`。
     *  如果`2i + 2 > n-1`，它无右子节点。

## 测试题 ##

**如果一棵完全二叉树有`768`个节点，求叶子节点的个数**？

假设叶子节点个数为`n0`，度为`1`的节点个数为`n1`，度为`2`的节点个数为`n2`。

总结点个数`n = n0 + n1 + n2`，而且`n0 = n2 + 1`，所以有`n = 2 * n0 + n1 - 1`。

完全二叉树的`n1`要么为`0`，要么为`1`

`n1`为`1`时，`n = 2 * n0`，`n`必然是偶数：

叶子节点个数`n0 = n / 2`，非叶子节点个数`n1 + n2= n/2`。

`n1`为`0`时，`n = 2 * n0 - 1`，`n`必然是奇数：  
              叶子节点个数`n0 = (n + 1)/ 2`，非叶子节点个数`n1 + n2 = (n- 1)/2`。

# 9. 构建二叉树 #

倘若，我们想要构建下图所示的一棵二叉树，应该如何构建呢？

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 5]

采用递归的方式，首先可以构建根节点，然后构建根节点的左子树，接着构建根节点右子树。  
       既然采用递归，那么一定得有递归的终止条件，那么何时终止呢？答案便是节点为`NULL`的时候，这里我们以`#`字符代替空节点。

接下来，便进入代码的研究。

首先，我们可以看一下，二叉树节点的定义。

/** * @author wangzhao * @date 2020/7/1 2:11 */
    public class TreeNode<E> { 
    
        public E value;
        public TreeNode<E> left;
        public TreeNode<E> right;
        public TreeNode<E> parent;
    
        public TreeNode(E value, TreeNode<E> parent) { 
            this.value = value;
            this.parent = parent;
        }
    }

相比于前面介绍的二叉树，多了一个`parent`指针，不过这并不影响我们对二叉树的使用，这样定义是为了后面其他树的学习。

二叉树的构建代码可以看`createTree()`方法。

import	java.util.Scanner;
    import	java.util.Scanner;/** * @author wangzhao * @date 2020/7/1 2:10 */
    public class BinaryTree { 
    
        private TreeNode root;
    
        public TreeNode createTree(){ 
            root = createTree(null);
            return root;
        }
    
        private TreeNode createTree(TreeNode parentNode){ 
            Scanner input = new Scanner(System.in);
            char ch = input.next().charAt(0);
            // 递归的终止条件
            if (ch == '#'){ 
                return null;
            }
            // 首先构建根节点
            TreeNode node = new TreeNode(ch, parentNode);
            // 接着构建根节点的左子树
            node.left = createTree(node);
            // 最后构建根节点的右子树
            node.right = createTree(node);
            return node;
        }
    }

如果，我们要构建上图所示的二叉树，输入的内容应该如下所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 6]

# 10. 二叉树的遍历 #

## 前序遍历 ##

*  访问顺序

根节点、左子树、右子树

前序遍历二叉树的顺序如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 7]

public void preOrderTraversal(){ 
            preOrderTraversal(root);
        }
    
        private void preOrderTraversal(TreeNode node){ 
            if (node == null)
                return;
            // 首先打印当前根节点的值
            System.out.println(node.value);
            // 接着遍历当前根节点的左子树
            preOrderTraversal(node.left);
            // 最后遍历当前根节点的右子树
            preOrderTraversal(node.right);
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 8]

## 中序遍历 ##

*  访问顺序

左子树、根节点、右子树

中序遍历二叉树的顺序如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 9]

public void inOrderTraversal(){ 
            inOrderTraversal(root);
        }
    
        private void inOrderTraversal(TreeNode node){ 
            if (node == null)
                return;
            // 首先当前根节点的左子树
            inOrderTraversal(node.left);
            // 接着打印当前根节点的值
            System.out.println(node.value);
            // 最后遍历当前根节点的右子树
            inOrderTraversal(node.right);
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 10]

## 后序遍历 ##

*  访问顺序

左子树、右子树、根节点

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 11]

public void postOrderTraversal(){ 
            postOrderTraversal(root);
        }
    
        private void postOrderTraversal(TreeNode node){ 
            if (node == null)
                return;
            // 首先当前根节点的左子树
            postOrderTraversal(node.left);
            // 接着遍历当前根节点的右子树
            postOrderTraversal(node.right);
            // 最后打印当前根节点的值
            System.out.println(node.value);
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 12]

## 层序遍历 ##

*  访问顺序

从上到下，从左到右依次访问每一个节点。

*  实现思路

1.  将根节点入队
2.  循环执行以下操作，直到队列为空
    
     *  将队头节点`root`出队，进行访问
     *  将`root`的左子节点入队
     *  将`root`的右子节点入队

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 13]

public void sequenceTraversal(){ 
            if (root == null){ 
                return;
            }
            Queue<TreeNode> queue = new LinkedList<TreeNode> ();
            queue.offer(root);
            while (!queue.isEmpty()){ 
                // 根节点出队
                TreeNode node = queue.poll();
                // 根节点的左子树入队
                if (node.left != null){ 
                    queue.offer(node.left);
                }
                // 根节点的右子树入队
                if (node.right != null){ 
                    queue.offer(node.right);
                }
                System.out.println(node.value);
            }
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 14]

# 11. 遍历的应用 #

*  前序遍历

树状结构展示(注意左右子树的顺序)。

*  中序遍历

二叉搜索树的中序遍历按升序或者降序处理节点。

*  后序遍历

适用于一些先子后父的操作。

*  层序遍历

计算二叉树的高度。

判断一棵树是否为完全二叉树。

## 树状打印二叉树 ##

@Override
        public String toString() { 
            StringBuilder sb = new StringBuilder();
            toString(root, sb, "");
            return sb.toString();
        }
    
        private void toString(TreeNode root, StringBuilder sb, String prefix) { 
            if (root == null){ 
                return;
            }
            sb.append(prefix).append(root.value).append("\n");
            toString(root.left, sb, prefix + "[L] ");
            toString(root.right, sb, prefix + "[R] ");
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 15]

## 计算二叉树的高度 ##

方式一：二叉树的高度等于左子树和右子树高度的最大值+1。

public int height() { 
            return height(root);
        }
    
        private int height(Node<E> root) { 
            if(rootNode == null)
                return 0;
            return 1 + Math.max(height(root.left), height(root.right));
        }

方式二：层序遍历中，当每遍历完该层的最后一个节点，则高度+1。

如何判断当前节点是否是该层的最后一个节点，如果当前遍历的节点是该层的最后一个节点，那么下一层节点的个数就等于队列中元素的个数。

public int height() { 
            if (rootNode == null)
                return 0;
            // 存储着每一层元素的数量
            int height = 0;
            int levelSize = 1;
            Queue<Node> queue = new LinkedList<Node> ();
            queue.offer(rootNode);
            while (!(queue.isEmpty())){ 
                Node node = queue.poll();
                levelSize--;
                if (node.left != null){ 
                    queue.offer(node.left);
                }
                if (node.right != null){ 
                    queue.offer(node.right);
                }
                if (levelSize == 0){  // 访问完当前层的最后一个元素
                    levelSize = queue.size();
                    height++;
                }
            }
            return height;
        }

## 判断一棵树是否为完全二叉树 ##

完全二叉树的定义如下：叶子节点只会出现最后`2`层，且最后`1`层的叶子结点都靠左对齐。

*  如果树为空，返回`false`。
 *  如果树不为空，开始层序遍历二叉树（队列）
    
     *  如果`node.left != null`，将`node.left`入队。
     *  如果`node.left == null && node.right != null`，返回`false`。
     *  如果`node.right !=null`，将`node.right`入队。
     *  如果`node.right == null`
        
         *  那么后面遍历的节点应该都为叶子节点，才是完全二叉树
         *  否则返回`false`
     *  遍历结束，返回`true`。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 16]  
       例如，节点`B`的`right`为`null`时，那么其后面的节点`C`和`D`只有是叶子节点时才能是完全二叉树。

public boolean isComplete(){ 
            if (root == null)
                return false;
            boolean leaf = false;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()){ 
                TreeNode node = queue.poll();
                if (leaf && (node.right != null || node.left != null)){ 
                    return false;
                }
                if (node.left != null){ 
                    queue.offer(node);
                }else if (node.right != null){ 
                    // node.left == null && node.right != null
                    return false;
                }
                if (node.right != null){ 
                    queue.offer(node);
                }else{ 
                    // 此时，后续节点需要都是叶子节点
                    leaf = true;
                }
            }
            return true;
        }

## 翻转二叉树 ##

[翻转二叉树][Link 1]

前序、中序、后序、层序都可以做，只要可以遍历到每一个节点。

// 采用前序遍历的方式
        public TreeNode invertTree(TreeNode root) { 
            if(root == null){ 
                return null;
            }
            TreeNode tempNode = root.left;
            root.left = root.right;
            root.right = tempNode;
            invertTree(root.left);
            invertTree(root.right);
            return root;
        }

// 采用中序遍历的方式
        public TreeNode invertTree(TreeNode root) { 
            if(root == null){ 
                return null;
            }
            invertTree(root.left);
            TreeNode tempNode = root.left;
            root.left = root.right;
            root.right = tempNode;
            // 注意，这里因为已经将左右节点进行交换了，所以需要对 left 进行交换，即交换前的right 节点
            invertTree(root.left);
            return root;
        }

// 采用后序遍历的方式
        public TreeNode invertTree(TreeNode root) { 
            if(root == null){ 
                return null;
            }
            invertTree(root.left);
            invertTree(root.right);
            TreeNode tempNode = root.left;
            root.left = root.right;
            root.right = tempNode;
            return root;
        }

// 采用层序遍历的方式
        public TreeNode invertTree(TreeNode root) { 
            if(root == null){ 
                return null;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()){ 
                TreeNode node = queue.poll();
                TreeNode tempNode = node.left;
                node.left = node.right;
                node.right = tempNode;
                if(node.left != null){ 
                    queue.offer(node.left);
                }
                if(node.right != null){ 
                    queue.offer(node.right);
                }
            }
            return root;
        }

## 重建二叉树 ##

[重建二叉树][Link 2]

通过以下结果可以保证重建出一棵唯一的二叉树。

*  前序遍历 + 中序遍历
 *  后序遍历 + 中序遍历

这里，我们以前序+中序的方式为例。首先，在前序遍历中，可以确定根节点。然后再中序遍历确定根节点的位置。根节点的左边则为左子树，右边则为右子树。接着回到前序遍历的左右子树，分别确定其根节点，接着再回到中序遍历中对应左右子树中寻找根节点，一直递归。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 17]

索引关系如图示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 18]

public TreeNode buildTree(int[] preorder, int[] inorder) { 
            TreeNode root = null;
            root = buildTree(preorder, 0, preorder.length-1, inorder, 0, inorder.length - 1);
            return root;
        }
    
        private TreeNode buildTree(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) { 
    
            if (preLeft > preRight || inLeft > inRight){ 
                return null;
            }
    
            TreeNode root = new TreeNode(preorder[preLeft]);
            int i = 0;
            // 中序遍历中寻找根节点的位置
            for (i = inLeft; i <= inRight; i++){ 
                if (preorder[preLeft] == inorder[i]){ 
                    break;
                }
            }
            // 构建左子树
            root.left = buildTree(preorder, preLeft + 1, preLeft + i - inLeft, inorder, inLeft, i - 1);
            // 构建右子树
            root.right = buildTree(preorder, preLeft + i - inLeft + 1, preRight, inorder, i + 1, inRight);
            return root;
        }

## 前驱节点 ##

*  前驱节点:中序遍历时的前一个节点
    
     *  如果是二叉搜索树，前驱节点就是前一个比它小的节点

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 19]

*  `node.left != null`
    
     *  `processorNode = node.left.right.right ...` ，终止条件`right == null`
     *  例如`4`的前驱节点为`3`，`13`的前驱节点为`12`。
 *  `node.left == null && node.parent != null`
    
     *  `processorNode = node.parent.parent...`，终止条件`node = parent.right`
     *  例如`3`的前驱节点是`2`，`9`的前驱节点是`8`。
 *  `node.left == null && node.parent == null`
    
     *  无前驱节点

public TreeNode predecessorNode(TreeNode node){ 
            if (node == null){ 
                return null;
            }
            // 前驱节点在左子树中
            TreeNode processorNode = node.left;
            if (processorNode != null){ 
                while (processorNode.right != null){ 
                    processorNode = processorNode.right;
                }
                return processorNode;
            }
    
            // 从祖先节点中寻找
            while (node.parent != null && node == node.parent.left){ 
                node = node.parent;
            }
    
            // node.parent == null
            // node == node.parent.right
            return node.parent;
        }

## 后继节点 ##

*  后继节点：中序遍历时的后一个节点
    
     *  如果是二叉搜索树，后继节点就是后一个比它大的节点
 *  `node.right != null`
    
     *  `successor = node.right.left.left.left...`，终止条件: `left == null`
 *  `node.right == null && node .parent != null`
    
     *  `successor = node.parent.parent.parent...`，终止条件：`node == node.parent.left`
 *  `node.right == null && node.parent == null`
    
     *  那就没有前驱节点

public TreeNode successorNode(TreeNode node){ 
            if (node == null){ 
                return null;
            }
            // 后继节点在右子树中
            TreeNode successorNode= node.right;
            if (successorNode!= null){ 
                while (successorNode.left!= null){ 
                    successorNode= successorNode.left;
                }
                return successorNode;
            }
    
            // 从祖先节点中寻找
            while (node.parent != null && node == node.parent.right){ 
                node = node.parent;
            }
    
            return node.parent;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70]: /images/20210813/0bd34f62747d4e47b5f10e759b6ef551.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 1]: /images/20210813/d76393e7334f4819b07c2b1111b2d40b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 2]: /images/20210813/d6c2ee37fc0349ec87092e24346106bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 3]: /images/20210813/50765d23eb2749f0af9b11d008e244e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 4]: /images/20210813/d9c843ec66b34ad1915d4a7999094647.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 5]: /images/20210813/6d622c48547145b9af2c825f727dae39.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 6]: /images/20210813/76f8b470c68e4cae902c1767df1e779f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 7]: /images/20210813/f2ff9d2a0df04fafbbbfe238f3748ac9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 8]: /images/20210813/5f17a9ee30f24e2ebaca54511df021ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 9]: /images/20210813/cceab2549d174abba4d07bc6b9e15427.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 10]: /images/20210813/970f99f212cd45f7b52844c673e25be4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 11]: /images/20210813/744061da95894be98d43f64af3beaa30.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 12]: /images/20210813/32975577cc354ac997d47c536cbf641b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 13]: /images/20210813/724b309fbfe24b6b9b9251902c4eebbb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 14]: /images/20210813/a25fe36e00744c49bd7b3f9e5a7fe49d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 15]: /images/20210813/b37f33f309b9407ca8aed3799c64fedb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 16]: /images/20210813/822b50c8697d4edca15063f3b6eb5908.png
[Link 1]: https://leetcode-cn.com/problems/invert-binary-tree/
[Link 2]: https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 17]: /images/20210813/c184c448cabc4224a429d43ed8f35407.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 18]: /images/20210813/38966930b13c4fdaa6b4a76f8d09adde.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 19]: /images/20210813/8cb08bc6a8d340aead49cfc378d561bd.png