社区首页 >专栏 >二叉树oj题解析

二叉树oj题解析

如烟花般绚烂却又稍纵即逝

发布于 2024-11-26 00:43:29

11400

代码可运行

文章被收录于专栏：javajava

运行总次数：0

代码可运行

二叉树的最近公共祖先

什么是最近公共祖先？

最近的公共祖先指的是这一棵树中两个节点中深度最大的且公共的祖先节点就是最近祖先节点。 也就是说这两个节点在树中距离最近的相交 例如：8 与6中的最近公共节点为2，因为他的最大深度就是2（在同一颗子树中）。 8与4的最近公共节点为3，因为他的最大深度是3（在左右两棵子树中的情况）。

leetcode中求二叉树中最近公共祖先

解题1.

公共祖先的三种形式： 1.题中可知：如果root根节点为q或者p，root这个节点就是最近的公共祖先节点。 2.如果p和q各自在原根节点的左右两棵子树中，则原根节点就是p和q的最近公共祖先。 3.如果p和q在根节点的同一颗子树中，则p和q的相遇之后两个节点最大深度且相交平行的第一个节点，就是最近公共祖先

  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)return null;
        //q或者p如果在其中的根节点上直接返回
       if(root==p||root==q)return root;
       //向左开始递归每一棵左右树
     TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
    TreeNode rightTree= lowestCommonAncestor(root.right,p,q);
       //说明两棵树都不为null
       if(leftTree!=null&&rightTree!=null){
        return root;
       }else if(leftTree!=null){
        return leftTree;
       }else{
        return rightTree;
       }
    }
}

解题2.

前面我们也说过p和p两个节点的最大深度就是它两个的最近公共祖先，也就是相交的节点，这里的B就是它们两个的公共祖先。 那我们为什么不能将两个节点的以相同的距离开始走，最后两个节点的值相同就是最近公共祖先

假如两个节点到最近公共祖先的距离相同。 我们可以创建两个栈分别来存储到达p和q距离的所有节点，假设距离相同后pop出栈，如果出栈过程中两个节点的值相同就是它两个的公共祖先了。

这里我们如果遇到了多余的子树节点就返回false，并将其出栈，然后继续找p或者q节点找到后直接返回true。

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)return null;
        Stack<TreeNode> stackP=new Stack<>();
        Stack<TreeNode> stackQ=new Stack<>();
        getTNodeLocation(root,stackP,p);
        getTNodeLocation(root,stackQ,q);
        //获取两个栈点的大小
        int sizeP=stackP.size();
        int sizeQ=stackQ.size();
        if(sizeP>sizeQ){
            int size = sizeP-sizeQ;
            while(size!=0){
                stackP.pop();
                size--;
            }
        }else{
            int size = sizeQ-sizeP;
           while(size!=0){
             stackQ.pop();
            size--;
           }
        }
        //找到两者的最近公共祖先
        while(!stackQ.isEmpty()&&!stackP.isEmpty()){
            if(stackQ.peek()==stackP.peek()){
                return stackQ.peek();
            }else{
                stackQ.pop();
                stackP.pop();
            }
        }
        return null;
    }
    //将指定的节点放入到栈中
    private boolean getTNodeLocation(TreeNode root,Stack stack,TreeNode t){
        //如果为null，返回给上一个节点false
        if(root==null)return false;
        stack.push(root);//走一步放入栈一个节点
        if(root==t)return true;//这里root如果为t直接返回
       boolean judg1 =  getTNodeLocation(root.left,stack,t);
       if(judg1==true)return true;
       boolean judg2 =  getTNodeLocation(root.right,stack,t);
       if(judg2==true)return true;
       stack.pop();//这里将出多余的节点出栈
       return false;
    }

根据二叉树创建字符串

这里的题意：对二叉树根节点进行前序的遍历，将遍历到的子树通过括号括起来，如果左子树有节点但是右子树没有节点，则将多余的右子树的括号省略，当右子树有节点但是左子树没有节点时，将左子树节点的括号添加进去。 这里的条件是：1.左子树如果为空，右子树不为空时，左右子树都有括号。 2.左子树不为空时，右子树为空，则可以忽略右树括号。

   public String tree2str(TreeNode root) {
        StringBuilder sb=new StringBuilder();
        tree2strChild(root,sb);
        return sb.toString();
    }
    public void tree2strChild(TreeNode root,StringBuilder sb){
        if(root==null)return;
        sb.append(root.val);
        if(root.left!=null){
        sb.append("(");
        tree2strChild(root.left,sb);
        sb.append(")");
        }else{
            if(root.right!=null){
                sb.append("()");
            }
        }
        if(root.right!=null){
            sb.append("(");
            tree2strChild(root.right,sb);
            sb.append(")");
        }
    }