题解 | #牛群的树形结构展开# 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. 对于当前节点p，如果p的右子节点不为空，则将其入栈，以便在之后处理。
2. 将p的左子节点设为null，并将p的右子节点设置为p的原左子节点。
3. 如果原左子节点pl等于null，则说明已经处理完p的所有左子树节点，需要继续处理栈中的节点。如果栈为空，表示已经处理完整棵树，结束循环；否则，从栈中弹出一个节点并赋值给pl。
4. 将pl作为p的右子节点。
5. 将p更新为新的右子节点pl，并继续循环处理。