[数据结构与算法]力扣-114-二叉树展开为链表

点我查看原题

Java代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if(root == null) return;
        unfold(root);
    }

    static void unfold(TreeNode root){
    	//我们这里并不打算到树的叶子节点，因为这叶子节点也做不了什么操作，所以当进入叶子节点时直接退回。
        if(root.left == null && root.right == null)return;
        //二叉树的子节点可以分为三种情况，一是左右都为空，二是左为空，三是右为空
        //二情况不用考虑，一三可以一起处理
        if(root.left != null){
            unfold(root.left);
            TreeNode t = getright(root.left);
            t.right = root.right;
            root.right = root.left;
            root.left = null;
        }
        if(root.right != null){
            unfold(root.right);
        }
    }
	//原本是没有这个函数的，本来以为
	//root.left.right = roo.right就可以了
	//结果发现会丢失一部分元素，粗了
	//用while感觉好麻烦，突然想到可以递归，就写个工具函数
    static TreeNode getright(TreeNode root){
        if(root.right == null) return root;
        return getright(root.right);
    }
}