题解 | #牛群的树形结构展开# java

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return TreeNode类
     */
    public TreeNode flattenTree (TreeNode root) {
        // write code here
        if (root == null) return null;

        TreeNode p = root;
        Stack<TreeNode> stack = new Stack<>();

        while (p != null) {
            if (p.right != null) {
                stack.push(p.right);
            }

            TreeNode pl = p.left;
            p.left = null;

            if (pl == null) {
                if (stack.isEmpty()) {
                    break;
                }

                pl = stack.pop();
            }

            p.right = pl;
            p = pl;
        }

        return root;
    }
}

该代码使用的编程语言是Java。

此代码考察了以下知识点：

1. 二叉树的结构定义：定义了一个 TreeNode 结构体，表示二叉树的节点。
2. 栈（Stack）的使用：通过栈来辅助实现二叉树的展开操作。
3. 二叉树的展开：将二叉树展开为一个只有右子节点的链表形式。
4. 迭代遍历：通过迭代方式遍历二叉树的节点。

代码的文字解释大纲如下：

1. 定义了一个 TreeNode 结构体，包含一个整数值 val，以及左右子节点指针 left 和 right。
2. 创建了一个 Solution 类，包含了展开二叉树的方法 flattenTree。
3. flattenTree 方法接收一个根节点 root，并返回展开后的新树的根节点。如果根节点为空，直接返回空。使用一个栈 stack 来辅助展开操作。初始化栈，将根节点的右子节点（如果有）压入栈中。遍历树的每一个节点 p：将 p 的左子节点置为空，并获取其原来的左子节点 pl。如果 pl 为空，而且栈不为空，则从栈中弹出一个节点作为 pl。将 pl 赋给 p 的右子节点，并将 p 指向 pl。返回展开后的树的根节点。