树:当我踏上算法之路,我发现...

2020.09.30 08:09:46
39
阅读约 6 分钟

#

翻转二叉树(简单) #

题干:

/**
 * 输入
 *     4
 *    /   \
 *   2     7
 *  / \   / \
 * 1   3 6   9
 * 输出
 *     4
 *    /   \
 *   7     2
 *  / \   / \
 * 9   6 3   1
 */

解法:对于这种题目,我觉得可以将其分为三个步骤,第一是寻找终止条件,思考一下何时递归终止,其次就是左右节点需要分开处理。
我们可以这样拆分解答:

class Solution {
    public TreeNode invertTree(TreeNode root) {
            invert(root);
            return root;
    }

    private void invert(TreeNode node) {
    // 终止条件,节点为null时退出
        if(node==null) return;
    
    // 题目要求我们对每一层的树节点进行翻转,所以我们只需要处理递归到这一层即可
        TreeNode temp = node.left;
        node.left = node.right;
        node.right=temp;

    //  处理好这一层之后,进入左节点与右节点分别处理下一层
        invert(node.left);
        invert(node.right);
    }
}

二叉树的层级遍历 #

题干:
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)
例子:
二叉树:[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

深度优先搜索解法:

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>>  lists =  new ArrayList<>();
        leverOrder(root,lists,0);
     
        return  lists;
    }
    // 深度优先搜索解法
    private void leverOrder(TreeNode root, List<List<Integer>> lists,int dept) {
        // 终止条件
        if(root==null) return;
        
        //如果当前深度与list大小相等,添加新数组
        if(dept==lists.size())
        {
            lists.add(new ArrayList<>());
        }
   
        lists.get(dept).add(root.val);
        leverOrder(root.left,lists,dept+1);
        leverOrder(root.right,lists,dept+1);
        
    }
}

广度优先搜索的解法:

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root==null) return ret;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            ArrayList<Integer> level = new ArrayList<>();
            int curr = queue.size();
            for (int i = 1; i <= curr; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if(node.left!=null){
                    queue.add(node.left);
                }

                if(node.right!=null){
                    queue.add(node.right);
                }
            }
           ret.add(level);
        }

        return  ret;
    }
}

事实证明,深搜更快😀

二叉树的中序遍历 #

题干:
给定一个二叉树,返回它的中序 遍历。

中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。若二叉树为空则结束返回,否则:
(1)中序遍历左子树
(2)访问根结点
(3)中序遍历右子树

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

题解:

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> arrayList = new ArrayList<>();

        inorder(root,arrayList);

        return arrayList;
    }

    private void inorder(TreeNode root,List<Integer> arrayList) {
        if(root==null) return;
        // 若左节点不为空,则会从最底层的左节点开始添加节点值
        if(root.left!=null) {
            inorder(root.left,arrayList);
        }
        arrayList.add(root.val);
        if(root.right!=null) {
            inorder(root.right,arrayList);
        }
    }
}

前、中、后序的三种递归模板 #

前序打印

class Solution {
    public void inorderTraversal(TreeNode root) {
        inorder(root);
    }
    private void inorder(TreeNode root) {
        if(root==null) return;
        System.out.println(node.val);
        inorder(root.left);
        inorder(root.right);
    }
}

中序打印

class Solution {
    public void inorderTraversal(TreeNode root) {
        inorder(root);
    }
    private void inorder(TreeNode root) {
        if(root==null) return;
        inorder(root.left);
        System.out.println(node.val);
        inorder(root.right);
    }
}

后序打印

class Solution {
    public void inorderTraversal(TreeNode root) {
        inorder(root);
    }
    private void inorder(TreeNode root) {
        if(root==null) return;
        inorder(root.left);
        inorder(root.right);
        System.out.println(node.val);
    }
}

参考文献:
1:关于二叉树的前序、中序、后序三种遍历

把二叉搜索树转为累加树 #

二叉搜索树的特点:
img

  • 根节点大于左节点小于右节点

题干:
给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例子:

输入: 原始二叉搜索树:
              5
            /   \
           2     13

输出: 转换为累加树:
             18
            /   \
          20     13

分析:
根据二叉搜索树的特点,知道通过中序遍历可以得到从小到大的节点排序值,因此,我们可以通过这个特点,给出一个外部变量用于记录累加值,然后让每个节点都加上这个值即可。

解法:

class Solution {
    // 记录累加值
    int val = 0;
    public TreeNode convertBST(TreeNode root) {
        convert(root);
        return root;
    }

    private void convert(TreeNode root) {
        if(root==null) return ;

        if(root.right!=null){
            convert(root.right);
        }
        // 累加并赋值
         val+=root.val;
        root.val=val;
        if(root.left!=null){
            convert(root.left);
        }
    }
}

二叉搜索树的最近公共祖先 #

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

img

示例 1:

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

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

解法:

class Solution {
(begin)
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while (true) {
            if (p.val < ancestor.val && q.val < ancestor.val) {
                ancestor = ancestor.left;
            } else if (p.val > ancestor.val && q.val > ancestor.val) {
                ancestor = ancestor.right;
            } else {
                break;
            }
        }
        return ancestor;
(/end)
    }
}

二叉树的最近公共节点 #

题干同上,唯一不同点是该二叉树不是BST树

img

例子1:

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

例子2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

解答:

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null; // 如果树为空,直接返回null
        if(root == p || root == q) return root; // 如果 p和q中有等于 root的,那么它们的最近公共祖先即为root(一个节点也可以是它自己的祖先)
        TreeNode left = lowestCommonAncestor(root.left, p, q); // 递归遍历左子树,只要在左子树中找到了p或q,则先找到谁就返回谁
        TreeNode right = lowestCommonAncestor(root.right, p, q); // 递归遍历右子树,只要在右子树中找到了p或q,则先找到谁就返回谁
        if(left == null) return right; // 如果在左子树中 p和 q都找不到,则 p和 q一定都在右子树中,右子树中先遍历到的那个就是最近公共祖先(一个节点也可以是它自己的祖先)
        else if(right == null) return left; // 否则,如果 left不为空,在左子树中有找到节点(p或q),这时候要再判断一下右子树中的情况,如果在右子树中,p和q都找不到,则 p和q一定都在左子树中,左子树中先遍历到的那个就是最近公共祖先(一个节点也可以是它自己的祖先)
        else return root; //否则,当 left和 right均不为空时,说明 p、q节点分别在 root异侧, 最近公共祖先即为 root
    }
}
 

1:二叉搜索树

阅读:39 . 字数:1386 发布于 2 个月前
Copyright 2018-2020 Siques