二叉树OJ(JavaDS)

逃离我推掉我的手 2024-04-03 08:17 84阅读 0赞

#### 文章目录 ####

*  KY11 二叉树遍历
 *  力扣236.二叉树的最近公共祖先
 *   *  方法一
     *  方法二
 *  牛客JZ36 二叉搜索树与双向链表
 *  力扣144.二叉树前序非递归遍历实现

![在这里插入图片描述][ab72878e53ed4973a7ce1f2bd7fe41c9.png]

## KY11 二叉树遍历 ##

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

示例1
    输入：
    abc##de#g##f###
    输出：
    c b e g d f a

![在这里插入图片描述][f49202f871f64062a7c8ed2403964d5d.png]

import java.util.Scanner;
    
    // 注意类名必须为 Main, 不要有任何 package xxx 信息
    class TreeNode{
        
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val){
        
            this.val=val;
        } 
    }
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner in = new Scanner(System.in);
            // 注意 hasNext 和 hasNextLine 的区别
            while (in.hasNextLine()) {
         // 注意 while 处理多个 case
                String str=in.nextLine();
                TreeNode root=createTree(str);
                inorder(root);
            }
        }
        //中序遍历
        public static void inorder(TreeNode root){
        
            if(root==null){
        
                return;
            }
            inorder(root.left);
            System.out.print(root.val+" ");
            inorder(root.right);
        }
        public static int i=0;
        //全局，i只有一份
        
        public static TreeNode createTree(String str){
        
            TreeNode root=null;
            char ch=str.charAt(i);
            if(ch!='#'){
        
            //遍历字符串，如果是字符，就new一个结点，然后左边和右边递归
                root=new TreeNode(ch);
                i++;
                root.left=createTree(str);
                root.right=createTree(str);
            }else{
        
            //如果是‘#’,说明走到空的位置，就i++,继续遍历字符串，同时返回root的初始值null，返回到上一次递归
                i++;
            }
            return root;
        }
    }

## 力扣236.二叉树的最近公共祖先 ##

![在这里插入图片描述][48e23474f7254c3fb9cb97d4fec86fab.png]

示例 1：
    输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
    输出：3
    解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

### 方法一 ###

> 借助栈

> 可以联想到两个链表的公共节点问题

![在这里插入图片描述][55988927046c454daf1453a9c6ddcfe3.png]

> 那么如何找到两个元素的路径？

> 先创建一个栈，把root入栈，如果root==p，返回true回到上一次递归，否则就到root.left去找，没找到就去root.right找，都没找到就弹出栈顶元素，返回false

import java.util.Stack;
    
    public class Solution {
        
        class TreeNode{
        
            public char val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(char val){
        
                this.val=val;
            }
        }
        //方法1，借助栈
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            if(root==null||p==null||q==null){
        
                return null;
            }
            Stack<TreeNode> stack1=new Stack<>();
            getPath(root,p,stack1);
            Stack<TreeNode> stack2=new Stack<>();
            getPath(root,q,stack2);
            int size1=stack1.size();
            int size2=stack2.size();
            int size=0;
            if(size1>size2){
        
                size=size1-size2;
                for(int i=0;i<size;i++){
        
                    stack1.pop();
                }
            }else{
        
                size=size2-size1;
                for(int i=0;i<size;i++){
        
                    stack2.pop();
                }
            }
            while(stack1.peek()!=stack2.peek()){
        
                stack1.pop();
                stack2.pop();
            }
            return stack1.peek();
        }
        public boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){
        
            if(root==null||node==null){
        
                return false;
            }
            stack.push(root);
            if(root==node){
        
                return true;
            }
            boolean ret1=getPath(root.left,node,stack);
            if(ret1==true){
        
                return true;
            }
            boolean ret2=getPath(root.right,node,stack);
            if(ret2==true){
        
                return true;
            }
            stack.pop();
            return false;
        }

### 方法二 ###

![在这里插入图片描述][23432c22354c449f9bb589b9f65bebc9.png]

class Solution {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            if(root==null){
        
                return null;
            }
            if(root==p||root==q){
        
                return root;
            }
            TreeNode leftTree=lowestCommonAncestor(root.left,p,q);
            TreeNode rightTree=lowestCommonAncestor(root.right,p,q);
            if(leftTree!=null&&rightTree!=null){
        
            //两侧
                return root;
            }
            else if(leftTree!=null){
        
            //都在左边
                return leftTree;
            }
            else if(rightTree!=null){
        
            //都在右边
                return rightTree;
            }
            else{
        
                return null;
            }
        }
    }

## 牛客JZ36 二叉搜索树与双向链表 ##

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
    要求不能创建任何新的结点，只能调整树中结点指针的指向。返回链表中的第一个节点的指针

> 二叉搜索树：  
> 根节点的左边都比根节点小，根节点的右边都比根节点大。  
> 特点：中序遍历是有序的

![在这里插入图片描述][8acec6b32874443faa3275de12685e78.png]

> 在中序遍历递归的基础上做修改，使结点的left,right指向改变，最后返回root=8，题目要求返回链表第一个节点的指针，所以从8开始往左找，找到left=null的节点1即为链表的头结点

public class Solution {
        
        TreeNode prev = null;
        public TreeNode Convert(TreeNode pRootOfTree) {
        
            if (pRootOfTree == null) {
        
                return null;
            }
            
            ConvertChild(pRootOfTree);
            TreeNode head = pRootOfTree;
            
            while (head.left != null) {
        
                head = head.left;
            }
            return head;
        }
        public void ConvertChild(TreeNode pCur) {
        
            if (pCur == null) {
        
                return;
            }
            ConvertChild(pCur.left);
            pCur.left = prev;
            if (prev != null) {
        
                prev.right = pCur;
            }
            prev = pCur;
            ConvertChild(pCur.right);
        }
    }
    //迭代+递归修改指向

## 力扣144.二叉树前序非递归遍历实现 ##

> 借助栈

> cur指向root,cur不为空，把cur进栈，并且list.add()，然后cur往左走，如果cur走到空，栈弹出栈顶元素赋给top，cur指向top.right，如果栈弹空了，说明遍历结束

![在这里插入图片描述][6acfa40320a948fb8ea44bb84b33c840.png]

import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    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;
        }
    }
    
    public  class Solution {
        
            public List<Integer> preorderTraversal(TreeNode root) {
        
                List<Integer> list = new ArrayList<>();
                TreeNode cur = root;
                Stack<TreeNode> stack = new Stack<>();
                while (true) {
        
                    if (cur != null) {
        
                        stack.push(cur);
                        list.add(cur.val);
                        cur = cur.left;
                    }
                    //cur为空
                    else {
        
                        if (stack.isEmpty()) {
        
                            break;
                        }
                        TreeNode top = stack.pop();
                        cur = top.right;
                    }
                }
                return list;
            }
    }

[ab72878e53ed4973a7ce1f2bd7fe41c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/28e23f722a4440be90b3fb80b3ed66c5.png
[f49202f871f64062a7c8ed2403964d5d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/f6ee6e2404654bb2bbd7a493dc98dd92.png
[48e23474f7254c3fb9cb97d4fec86fab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/c0d4598a88cc424282ee6a7bc6b199e4.png
[55988927046c454daf1453a9c6ddcfe3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/881372ab4db64ca1b22c7df4aa5c5070.png
[23432c22354c449f9bb589b9f65bebc9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/b816c594a7274d209c71ca9d2f0272da.png
[8acec6b32874443faa3275de12685e78.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/7f45527c67ea4b6baa18135c2397b1d6.png
[6acfa40320a948fb8ea44bb84b33c840.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/b6dd60b6d6d041d7ad0312c412095ec1.png