LC刷题专题：二叉树；迭代；递归（897、1372、208）

文章目录

897.递增顺序搜索树
1372. 二叉树中的最长交错路径
208. 实现 Trie (前缀树)

897.递增顺序搜索树

https://leetcode.cn/problems/increasing-order-search-tree/description/
在这里插入图片描述
这道题目本身就是一个简单题：非常容易实现：只需要在递归或者迭代中序遍历的同时保存一个临时节点，随后每遍历到一个节点，就把当前节点放到临时节点的右边，同时将临时节点更改为当前遍历到的节点。
迭代版本：

class Solution {
    TreeNode ans = new TreeNode();
    public TreeNode increasingBST(TreeNode root) {
        TreeNode res = ans;
        Deque<TreeNode> dq = new ArrayDeque<>();
        if(root == null){
            return ans;
        }
        TreeNode cur = root;
        while(!dq.isEmpty() || cur != null){
            if(cur != null){
                dq.addLast(cur);
                cur = cur.left;
            }else{
                cur = dq.pollLast();
                TreeNode temp = cur.right;
                cur.left = null;
                ans.right = cur;
                ans = cur;
                cur = temp;
            }
        }
        return res.right;
    }
}

递归版本：

class Solution {
    TreeNode ans = new TreeNode();
    public TreeNode increasingBST(TreeNode root) {
        TreeNode res = ans;
        buildIncrementTree(root);
        return res.right;
    }
    public void buildIncrementTree(TreeNode root){
        if(root == null){
            return;
        }
        buildIncrementTree(root.left);
        TreeNode cur = new TreeNode(root.val);
        ans.right = cur;
        ans = cur;
        buildIncrementTree(root.right);
    }
}