二叉树终章

本文还是为二叉树的练习题

查看源图像

来看第一个题

二叉树的最近公共祖先

在这里插入图片描述

附上代码

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {       
        if(root == null){
            return null;
        }
        if(p == root || q == root) {
            return root;
        }
        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
        if(leftTree == null) {
            return rightTree;
        }
        if(rightTree == null) {
            return leftTree;
        }
        return root;
    }
}


逻辑清晰些

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(p == root || q == root) 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 {
            // 右树不为空，左数为空
            return rightTree;
        }
    }

}

完成了以上那么我们接下来在来一种方法

在这里插入图片描述

接下来就与求链表交点一个思路没啥难度，那么你能自己完成吗？？？

附上代码

class Solution {
   
    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 flg = getPath(root.left,node,stack);
        if(flg) {
            return true;
        }
        flg = getPath(root.right,node,stack);
        if(flg) {
            return true;
        }
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root,p,stack1);
        getPath(root,q,stack2);
        int size1 = stack1.size();
        int size2 = stack2.size();
        if(size1 > size2) {
            int ret = size1 - size2;
            while(ret != 0) {
                stack1.pop();
                ret--;
            }
              while(!stack1.isEmpty() && !stack2.isEmpty()) {
                    if(stack1.peek() == stack2.peek()) {
                        return stack1.peek();
                    }
                    stack1.pop();
                    stack2.pop();
             }
        }else {
                 int ret = size2 - size1;
            while(ret != 0) {
                stack2.pop();
                ret--;
            }
              while(!stack1.isEmpty() && !stack2.isEmpty()) {
                    if(stack1.peek() == stack2.peek()) {
                        return stack1.peek();
                    }
                    stack1.pop();
                    stack2.pop();
             }
        }
        return null;
    }
}

二叉搜索树与双向链表

接下来我们来看这道题

在这里插入图片描述

附上代码

public class Solution {
    TreeNode prev = null;
    public void inorder(TreeNode root) {
        if(root == null) {
            return;
        }
        inorder(root.left);
        root.left = prev;
      
        //这里如果 不加条件 root != null 
        // 就会出现 空指针异常
        if(prev != null) {
            prev.right = root;
        }
         prev = root;
        inorder(root.right);
       
       
    }
    public TreeNode Convert(TreeNode root) {
        // 创建完 了 双向链表那么就要 去找到 head 结点了
        if(root == null){
            return null;
        }
        inorder(root);
        TreeNode head = root;
        while(head.left != null) {
            head = head.left;
        }
        return head;
    }
}

从前序与中序遍历序列构造二叉树

在这里插入图片描述

附上代码

class Solution {
    public  int preIndex = 0;
    public   TreeNode createTreeBypandI(int[]preorder,int[]inorder,int inbegin,int inend) {
        if(inbegin > inend) {
            return null;
        }
       int ret = preorder[preIndex];
       TreeNode root = new TreeNode(ret);
        
       int rootIndex = findIndexOfI(inorder,inbegin,inend,ret);
       if(rootIndex == -1) {
           return null;
       }
       preIndex++;
       root.left = createTreeBypandI(preorder,inorder,inbegin,rootIndex - 1);
       root.right = createTreeBypandI(preorder,inorder,rootIndex+1,inend);
       return root;
    }
    public int findIndexOfI(int[]inorder,int inbegin,int inend,int key) {
        for(int i = inbegin;i<= inend;i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null) {
            return null;
        }
        return createTreeBypandI(preorder,inorder,0,inorder.length-1);
    }
}

从中序与后序遍历序列构造二叉树

在这里插入图片描述

附上代码

class Solution {
    public static  int posIndex = 0;
    public TreeNode c(int[]inorder,int[]postorder,int inbegin ,int inend) {
        if(inbegin > inend) {
            return null;
        }
        int ret = postorder[posIndex];
        TreeNode root = new TreeNode(ret);
        int rootIndex = findIndex(inorder,inbegin,inend,ret);
        if(rootIndex == -1) {
            return null;
        }
        posIndex--;
        // 注意 后序遍历 是 左子树 --> 右子树 --> 根随
        // 随意 这里需要先创建 右子树
        root.right = c(inorder,postorder,rootIndex + 1,inend);
        root.left = c(inorder,postorder,inbegin,rootIndex-1);
        return root;
    }
    public int findIndex(int[] inorder,int inbegin, int inend,int key) {
        for(int i = inbegin;i <= inend; i++){
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
            if(inorder == null || postorder == null) {
                return null;
            }
            // 初始化全局变量 preIndex
            posIndex = postorder.length-1;
            // c 创建 二叉树
            return c(inorder,postorder,0,inorder.length - 1);
    }
}

根据二叉树创建字符串

在这里插入图片描述

附上代码

class Solution {
    public void trreeToString(TreeNode root,StringBuilder sb) {
        if(root == null) {
            return;
        }
        sb.append(root.val);
        if(root.left != null) {
            // 根据刚刚分析  只要 root.left != null 我们 就需要添加一个 （
            sb.append("(");
            trreeToString(root.left,sb);
            sb.append(")");
        }else {
            // root.left == null
            if(root.right == null) {
                // 这里我们 刚刚分析，如果 root.right == null 说明此时 需要添加一个 ） ，
                //我们可以放到递归返回的地方添加
                return;
            }else{
                // root.right != null 这里我们就需要 添加一个()
                sb.append("()");
            }
        }
        //左树走完 来 右树
        if(root.right != null) {
            sb.append("(");
            trreeToString(root.right,sb);
            sb.append(")");
        }else {
            //root.right == null
            // 此时 树为空直接 return 出去即可
            return;
        }
    }
    public String tree2str(TreeNode root) {
        if(root == null) {
            return null;
        }
        StringBuilder sb = new StringBuilder();
        trreeToString(root,sb);
        return sb.toString();
    }
}

二叉树的前序遍历非递归

在这里插入图片描述

附上代码

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return list;
    }
}

二叉树的中序遍历非递归

在这里插入图片描述

附上代码

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
           // System.out.println(top.val+" ");
            ret.add(top.val);
            cur = top.right;
        }
        return ret;
    }
}

二叉树的后序遍历非递归

在这里插入图片描述

附上代码

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
         if(root == null) {
             return list;
         }
         TreeNode cur = root;
         TreeNode prev = null;
         while(cur != null || !stack.isEmpty()) {
             while(cur != null) {
                 stack.push(cur);
                 cur = cur.left;
             }
             TreeNode top = stack.peek();
             if(top.right == null || top.right == prev ) {
                 stack.pop();
                 list.add(top.val);
                prev = top;
             }else {
                 cur = top.right;
             }
         }
         return list;
    }
}