[数据结构与算法]关于二叉树的学习

问题一：

给定一个二叉树，找到该树中两个指定节点的最近公共祖先，（一个节点也可以是自己的祖先）

public class Test0818Tree {
    //给定一个二叉树，找到该树中两个指定节点的最近公共祖先，（一个节点也可以是自己的祖先）
    private TreeNode lca=null;//lca表示最近的公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
        if(root==null){
            return null;
        }
        findNode(root,p,q);
        return lca;
    }

    private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
        //看从root中出发能不能找到p和q，只要找到一个就返回true，都找不到返回false
        if(root==null){
            return false;
        }
        //递归按后序遍历查找
        int left=findNode(root.left,p,q)?1:0;
        int right=findNode(root.right,p,q)?1:0;

        int mid=(root==p||root==q)?1:0;
        //如果三个位置的和为0，表示没找到，返回false，只要找到1个或以上就返回true
        if(left+right+mid==2){
            lca=root;
        }
        return (left+right+mid>0);
    }

问题二：将二叉搜索树转换为排序双链表

 public TreeNode convert(TreeNode pRootOfTree){
        //基于递归完成双向链表构造，为了保证有序性，需要中序遍历

        if(pRootOfTree==null){
            return null;
        }
        //left和right代表双链表的前节点引用与下一个节点引用
        if(pRootOfTree.left==null&&pRootOfTree.right==null){
            return pRootOfTree;
        }
        //最终链表为左子树的链表+根节点+右子树的链表
        //先递归左子树，left是左子树这个链表根节点
        TreeNode left=convert(pRootOfTree.left);
        //左子树链表尾节点
        TreeNode leftTail=left;
        while (leftTail!=null&&leftTail.right!=null){
            //right相当于链表的next
            leftTail=leftTail.right;
        }
        //循环结束后，leftTail指向了左侧链表的尾部，把左子树和当前节点连在一起
        if(left!=null){
            leftTail.right=pRootOfTree;
            pRootOfTree.left=leftTail;
        }

        //递归转换右子树，把右子树也变成双向链表
        TreeNode right=convert(pRootOfTree.right);

        //把当前节点和右子树连在一起
        if(right!=null){
            right.left=pRootOfTree;
            pRootOfTree.right=right;
        }

        //返回新的链表的头节点
        return left==null?pRootOfTree:left;
    }

问题三：根据一颗树的前序，中序遍历构造二叉树

private int index;//代表当前访问到先序遍历中的第几个元素
    public TreeNode buildTree(int[] preoder,int[] inoder) {
        index=0;
        return buildTreeHelper(preoder,inoder,0,inoder.length);
    }

    private TreeNode buildTreeHelper(int[] preoder, int[] inoder, int left, int right) {
        //[left,right)这个区间表示当前preorder[index]这个节点对应的子树的中序遍历结果

        if(left>=right){
            //中序遍历结果为空，这个数就是空树
            return null;
        }
        if(index>=preoder.length){
            return null;//遍历元素结束
        }

        //根据当前根节点的值创建出根节点
        TreeNode root=new TreeNode(preoder[index]);
        index++;//处理下一个节点
        //根据该节点在中序遍历结果中的位置，把inoder数字划分成两个部分

        int pos=find(inoder,left,right,root.val);

        //[left,pos)表示当前root左子树的中序遍历结果
        //[pos+1,right）表示当前root到右子树中序遍历

        root.left=buildTreeHelper(preoder,inoder,left,pos);
        root.right=buildTreeHelper(preoder,inoder,pos+1,right);

        return root;
    }

    private int find(int[] inoder, int left, int right, int tofind) {
        for(int i=left;i<right;i++){
            if(inoder[i]==tofind){
                return i;
            }
        }
        return -1;
    }

问题四：根据一颗二叉树创建字符串

private StringBuilder sb=new StringBuilder();//sb表示最终得到的字符串结果
    private String Tree2Str(TreeNode t){
        if(t==null){
            return "";//得返回一个空字符串
        }
        //借助helper递归进行先序遍历
        helper(t);
        return sb.toString();
    }

    private void helper(TreeNode t){
        if(t==null){
            return;
        }
        //访问根节点，此处的访问操作追加字符串到sb中
        sb.append("(");
        sb.append(t.val);

        helper(t.left);

        if(t.left==null&&t.right!=null){
            sb.append("()");
        }

        helper(t.right);

        sb.append(")");
    }
}