java二叉树和为某一个值的路径如何实现?思路分享

KLQ 2020-04-16 16:04:51 java常见问答 3848

下面给大家分享的是二叉树和为某一个值的路径的java实现和思路,具体的包含了3种实现方式和思路,下面一起来了解一下。

题目:

输入一颗二叉树的根节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。

路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

注: 在返回值的list中,数组长度大的数组靠前。

思路1:

递归策略

代码实现:

import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
 
    public TreeNode(int val) {
        this.val = val;
 
    }
}
*/
public class Solution
{
    public ArrayList < ArrayList < Integer >> FindPath(TreeNode root, int target)
    {
        ArrayList < ArrayList < Integer >> paths = new ArrayList < ArrayList < Integer >> ();
        if (root == null) return paths;
        find(paths, new ArrayList < Integer > (), root, target);
        return paths;
    }
    public void find(ArrayList < ArrayList < Integer >> paths, ArrayList < Integer > path, TreeNode root, int target)
    {
        path.add(root.val);
        if (root.left == null && root.right == null)
        {
            if (target == root.val)
            {
                paths.add(path);
            }
            return;
        }
        ArrayList < Integer > path2 = new ArrayList < > ();
        path2.addAll(path);
        if (root.left != null) find(paths, path, root.left, target - root.val);
        if (root.right != null) find(paths, path2, root.right, target - root.val);
    }
}

思路2

代码实现:

import java.util.ArrayList;
public class Solution
{
    private ArrayList < ArrayList < Integer >> res = new ArrayList < > ();
    private ArrayList < Integer > list = new ArrayList < > ();
    public ArrayList < ArrayList < Integer >> FindPath(TreeNode root, int target)
    {
        if (root == null) return res;
        list.add(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null)
        {
            res.add(new ArrayList < Integer > (list));
        }
        FindPath(root.left, target);
        FindPath(root.right, target);
        list.remove(list.size() - 1);
        return res;
    }
}

思路3:

代码实现:

非递归实现, 出栈是后序遍历
private ArrayList < ArrayList < Integer >> listAll = new ArrayList < ArrayList < Integer >> ();
public ArrayList < ArrayList < Integer >> FindPath(TreeNode root, int target)
{
    Stack < TreeNode > stack = new Stack < TreeNode > ();
    HashMap < TreeNode, Boolean > rightDealed = new HashMap < > ();
    TreeNode node = root;
    while (node != null || stack.size() > 0)
    {
        if (node != null)
        {
            stack.push(node);
            System.out.println("push:" + node.val); //先序
            addPath(node, stack, target);
            node = node.left;
        }
        else
        {
            node = stack.peek();
            if (rightDealed.get(node) != null)
            { //已访问过右节点 该出栈了
                stack.pop();
                System.out.println("pop:" + node.val); //后序
                node = null;
            }
            else
            { //若未访问右节点先不出栈
                rightDealed.put(node, true);
                node = node.right;
            }
        }
    }
    return listAll;
}
public void addPath(TreeNode node, Stack < TreeNode > stack, int target)
{
    if (node.left == null && node.right == null)
    {
        ArrayList < Integer > list = new ArrayList();
        int total = 0;
        for (TreeNode treeNode: stack)
        {
            list.add(treeNode.val);
            total = total + treeNode.val;
            System.out.print(treeNode.val + " ");
        }
        if (total == target)
        {
            listAll.add(list);
        }
    }
}

以上的三种实现方式大家都了解了吗?更多Java实例,可以继续的来本站了解哦。